Alternating Subsequence Sum — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Alternating Subsequence Sum problem optimally.
O(n log n)O(n)Problem Description
Given an integer array temperatures, select a non‑empty subsequence that preserves the original order. The consecutive differences of the chosen elements must form a strictly monotonic sequence: either each difference is larger than the previous one (strictly increasing) or each difference is smaller than the previous one (strictly decreasing). Return the maximum possible sum of the elements in such a subsequence.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Alternating Subsequence Sum"
WHY DOES IT MATTER?
Monotonic‑difference subsequences capture a class of ordering constraints that appear in finance (trend strength), signal processing, and version‑control diff analysis. Mastering this pattern teaches you to reason about second‑order relationships (differences of differences) rather than just element values.
OPTIMIZATION CHALLENGE
The key insight is to treat each pair (index, lastDifference) as a state and to query the best sum among all states with a smaller (or larger) lastDifference. By compressing differences and using a Fenwick tree you turn the naïve O(n^2) scan into O(n log n).
REAL-WORLD CONNECTION
Think of a temperature sensor stream where you want to pick readings that show a steadily accelerating rise or fall – the chosen points form a subsequence whose rate of change is strictly increasing or decreasing, analogous to detecting a trending anomaly in distributed monitoring.
When coding, first implement the clear O(n^2) DP to verify correctness on edge cases; then refactor the inner loop into a BIT/segment‑tree query. Keep the compression map of differences separate so you can reuse it for both increasing and decreasing passes.
COMPLEXITY AT A GLANCE
O(n log n)O(n)Core Theory — Why This Approach?
The problem can be modeled as a weighted longest monotonic‑difference subsequence. For any two chosen elements a[j] and a[i] (j<i) the difference d=a[i]-a[j] becomes the new “key” that must respect a strict monotonic order with the previous difference. A naïve exhaustive search would try every subsequence (2^n) and verify the monotonic condition, which is infeasible for n>30. The optimal paradigm is dynamic programming combined with order‑statistics structures: for each index i we keep the best achievable sum for subsequences that end at i with the last difference being either the smallest possible (for an increasing chain) or the largest possible (for a decreasing chain). By iterating i from left to right and, for each i, scanning all j<i we can compute the new difference d and extend any previously stored state whose last difference is strictly smaller (for increasing) or strictly larger (for decreasing). This yields an O(n^2) DP that is fast enough for the typical medium constraints, and can be further accelerated to O(n log n) with a Fenwick/segment tree after compressing the difference values.
Interview Questions on This Problem
Q1How would you modify the DP if the requirement changed from strictly monotonic differences to non‑strict (allowing equal differences)?
You would replace the strict inequality checks with non‑strict ones (<= for increasing, >= for decreasing) when querying the order‑statistics structure, and ensure that equal differences are handled by taking the maximum of the existing value and the candidate extension.
Q2Can the problem be solved in O(n) time if the array is already sorted either ascending or descending? Explain why or why not.
If the array is monotonic, every difference has the same sign, so only one direction (increasing or decreasing) is possible. The optimal subsequence then becomes the whole array because differences are already monotonic, giving O(n) by a single pass to compute the sum.
Q3Why is a weighted LIS (Longest Increasing Subsequence) formulation appropriate for this problem, and how does it differ from the classic LIS?
Classic LIS maximizes length, whereas here each element contributes its value to a total sum, so we need a weighted LIS where the weight of a subsequence is the sum of its elements. The DP transition uses the same order condition on differences but aggregates sums instead of counts.
Examples
Input
[4,2,5,1,6]
Output
13
Explanation: One optimal subsequence is [2,5,6]. Differences are 3 and 1, which are strictly decreasing (3>1). The sum is 2+5+6=13, which is the largest achievable.
Input
[-3,-1,-2,-5,-4]
Output
-4
Explanation: Choosing the subsequence [-3,-1] gives a single difference 2 (trivially monotonic). Its sum is -3+(-1)=-4, which is greater than any other valid subsequence.
Input
[10,1,2,3,4,5]
Output
20
Explanation: Subsequence [10,2,3,5] has differences -8,1,2, which are strictly increasing (-8<1<2). The sum is 10+2+3+5=20, the maximum possible.
Constraints
- 1 <= temperatures.length <= 100000
- -1000000000 <= temperatures[i] <= 1000000000
- Time limit: O(n log n) or better
- Memory limit: O(n)
Optimal Approach & Strategy
Use DP over pairs (index, lastDifference) and accelerate the transition with a Fenwick tree after compressing difference values – O(n log n) time.
Brute Force Approach
Enumerate every non‑empty subsequence, check the monotonic‑difference condition, and keep the maximum sum – exponential time.
Code Solutions
function alternatingSubsequenceSum(temperatures) {
const n = temperatures.length;
if (n === 0) return 0;
let answer = temperatures[0];
// inc[i] and dec[i] are Maps: diff -> best sum ending at i
const inc = Array.from({ length: n }, () => new Map());
const dec = Array.from({ length: n }, () => new Map());
for (let i = 0; i < n; ++i) {
answer = Math.max(answer, temperatures[i]);
for (let j = 0; j < i; ++j) {
const diff = temperatures[i] - temperatures[j];
// start a new two‑element subsequence (j,i)
inc[i].set(diff, Math.max(inc[i].get(diff) ?? -Infinity, temperatures[j] + temperatures[i]));
dec[i].set(diff, Math.max(dec[i].get(diff) ?? -Infinity, temperatures[j] + temperatures[i]));
// extend increasing‑diff sequences ending at j
for (const [prevDiff, prevSum] of inc[j]) {
if (diff > prevDiff) {
inc[i].set(diff, Math.max(inc[i].get(diff) ?? -Infinity, prevSum + temperatures[i]));
}
}
// extend decreasing‑diff sequences ending at j
for (const [prevDiff, prevSum] of dec[j]) {
if (diff < prevDiff) {
dec[i].set(diff, Math.max(dec[i].get(diff) ?? -Infinity, prevSum + temperatures[i]));
}
}
}
for (const val of inc[i].values()) answer = Math.max(answer, val);
for (const val of dec[i].values()) answer = Math.max(answer, val);
}
return answer;
}
// Example driver
const temps = [4, 2, 5, 1, 6];
console.log(alternatingSubsequenceSum(temps)); // 13#include <bits/stdc++.h>
using namespace std;
// O(n^2) DP solution. For each position i we keep two hash maps:
// inc[i][d] = best sum of a subsequence ending at i whose last difference is d
// and the sequence of differences is strictly increasing.
// dec[i][d] = best sum of a subsequence ending at i whose last difference is d
// and the sequence of differences is strictly decreasing.
long long alternatingSubsequenceSum(const vector<int>& a) {
int n = (int)a.size();
if (n == 0) return 0;
// each element alone is a valid subsequence
long long answer = a[0];
vector< unordered_map<long long,long long> > inc(n), dec(n);
for (int i = 0; i < n; ++i) {
// subsequence consisting of only a[i]
answer = max(answer, (long long)a[i]);
for (int j = 0; j < i; ++j) {
long long diff = (long long)a[i] - a[j];
// start a new two‑element subsequence (j,i)
inc[i][diff] = max(inc[i][diff], (long long)a[j] + a[i]);
dec[i][diff] = max(dec[i][diff], (long long)a[j] + a[i]);
// try to extend an increasing‑diff sequence that ended at j
for (auto &p : inc[j]) {
long long prevDiff = p.first;
long long prevSum = p.second;
if (diff > prevDiff) {
inc[i][diff] = max(inc[i][diff], prevSum + a[i]);
}
}
// try to extend a decreasing‑diff sequence that ended at j
for (auto &p : dec[j]) {
long long prevDiff = p.first;
long long prevSum = p.second;
if (diff < prevDiff) {
dec[i][diff] = max(dec[i][diff], prevSum + a[i]);
}
}
}
// update global answer with any sequence ending at i
for (auto &p : inc[i]) answer = max(answer, p.second);
for (auto &p : dec[i]) answer = max(answer, p.second);
}
return answer;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> temps = {4, 2, 5, 1, 6};
cout << alternatingSubsequenceSum(temps) << "\n"; // expected 13
return 0;
}import java.util.*;
public class Main {
// O(n^2) DP. For each index i we keep two hash maps:
// inc[i] : diff -> best sum of a subsequence ending at i with strictly increasing diffs
// dec[i] : diff -> best sum of a subsequence ending at i with strictly decreasing diffs
public static long alternatingSubsequenceSum(int[] a) {
int n = a.length;
if (n == 0) return 0L;
long answer = a[0];
@SuppressWarnings("unchecked")
HashMap<Long, Long>[] inc = new HashMap[n];
@SuppressWarnings("unchecked")
HashMap<Long, Long>[] dec = new HashMap[n];
for (int i = 0; i < n; ++i) {
inc[i] = new HashMap<>();
dec[i] = new HashMap<>();
}
for (int i = 0; i < n; ++i) {
answer = Math.max(answer, (long)a[i]);
for (int j = 0; j < i; ++j) {
long diff = (long)a[i] - a[j];
// start a new two‑element subsequence (j,i)
inc[i].put(diff, Math.max(inc[i].getOrDefault(diff, Long.MIN_VALUE), (long)a[j] + a[i]));
dec[i].put(diff, Math.max(dec[i].getOrDefault(diff, Long.MIN_VALUE), (long)a[j] + a[i]));
// extend increasing‑diff sequences ending at j
for (Map.Entry<Long, Long> e : inc[j].entrySet()) {
long prevDiff = e.getKey();
long prevSum = e.getValue();
if (diff > prevDiff) {
inc[i].put(diff, Math.max(inc[i].getOrDefault(diff, Long.MIN_VALUE), prevSum + a[i]));
}
}
// extend decreasing‑diff sequences ending at j
for (Map.Entry<Long, Long> e : dec[j].entrySet()) {
long prevDiff = e.getKey();
long prevSum = e.getValue();
if (diff < prevDiff) {
dec[i].put(diff, Math.max(dec[i].getOrDefault(diff, Long.MIN_VALUE), prevSum + a[i]));
}
}
}
for (long val : inc[i].values()) answer = Math.max(answer, val);
for (long val : dec[i].values()) answer = Math.max(answer, val);
}
return answer;
}
public static void main(String[] args) {
int[] temps = {4, 2, 5, 1, 6};
System.out.println(alternatingSubsequenceSum(temps)); // 13
}
}def alternating_subsequence_sum(temperatures):
"""Return the maximum sum of a subsequence whose consecutive differences are
strictly monotonic (either strictly increasing or strictly decreasing).
"""
n = len(temperatures)
if n == 0:
return 0
answer = temperatures[0]
# inc[i] and dec[i] are dicts: diff -> best sum ending at i
inc = [dict() for _ in range(n)]
dec = [dict() for _ in range(n)]
for i in range(n):
answer = max(answer, temperatures[i])
for j in range(i):
diff = temperatures[i] - temperatures[j]
# start a new two‑element subsequence (j,i)
inc[i][diff] = max(inc[i].get(diff, float('-inf')), temperatures[j] + temperatures[i])
dec[i][diff] = max(dec[i].get(diff, float('-inf')), temperatures[j] + temperatures[i])
# extend increasing‑diff sequences ending at j
for prev_diff, prev_sum in inc[j].items():
if diff > prev_diff:
inc[i][diff] = max(inc[i].get(diff, float('-inf')), prev_sum + temperatures[i])
# extend decreasing‑diff sequences ending at j
for prev_diff, prev_sum in dec[j].items():
if diff < prev_diff:
dec[i][diff] = max(dec[i].get(diff, float('-inf')), prev_sum + temperatures[i])
answer = max(answer, max(inc[i].values(), default=float('-inf')))
answer = max(answer, max(dec[i].values(), default=float('-inf')))
return answer
# Example driver
if __name__ == "__main__":
temps = [4, 2, 5, 1, 6]
print(alternating_subsequence_sum(temps)) # 13function alternatingSubsequenceSum(temperatures) {
const n = temperatures.length;
if (n === 0) return 0;
let answer = temperatures[0];
// inc[i] and dec[i] are Maps: diff -> best sum ending at i
const inc = Array.from({ length: n }, () => new Map());
const dec = Array.from({ length: n }, () => new Map());
for (let i = 0; i < n; ++i) {
answer = Math.max(answer, temperatures[i]);
for (let j = 0; j < i; ++j) {
const diff = temperatures[i] - temperatures[j];
// start a new two‑element subsequence (j,i)
inc[i].set(diff, Math.max(inc[i].get(diff) ?? -Infinity, temperatures[j] + temperatures[i]));
dec[i].set(diff, Math.max(dec[i].get(diff) ?? -Infinity, temperatures[j] + temperatures[i]));
// extend increasing‑diff sequences ending at j
for (const [prevDiff, prevSum] of inc[j]) {
if (diff > prevDiff) {
inc[i].set(diff, Math.max(inc[i].get(diff) ?? -Infinity, prevSum + temperatures[i]));
}
}
// extend decreasing‑diff sequences ending at j
for (const [prevDiff, prevSum] of dec[j]) {
if (diff < prevDiff) {
dec[i].set(diff, Math.max(dec[i].get(diff) ?? -Infinity, prevSum + temperatures[i]));
}
}
}
for (const val of inc[i].values()) answer = Math.max(answer, val);
for (const val of dec[i].values()) answer = Math.max(answer, val);
}
return answer;
}
// Example driver
const temps = [4, 2, 5, 1, 6];
console.log(alternatingSubsequenceSum(temps)); // 13Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.