Subsequence DP — max sum increasing, longest with adjacent diff one, no three consecutive, alternating, product < K, chain of pairs
Problem
Variations on LIS and House Robber:
Maximum sum increasing subsequence. The longest subsequence where adjacent elements differ by exactly 1. The maximum sum with no three consecutive elements taken. The longest alternating (zig-zag) subsequence. The number of subsequences with product less than k. The longest chain of pairs, where (a, b) can be followed by (c, d) only if b < c.
Example 1
Input: max sum increasing: [1, 101, 2, 3, 100, 4, 5] Output: 106
1 + 2 + 3 + 100.
Also asked as: Maximum Sum Increasing Subsequence · Longest subsequence such that difference between adjacent is one · Maximum subsequence sum such that no three are consecutive · Longest alternating subsequence · Count all subsequences having product less than K · Maximum Length Chain of Pairs · Maximum Length of Pair Chain · Maximum sum of pairs with specific difference
Test cases
Case 1
Input: [1,101,2,3,100,4,5] Expected: 106
Case 2
Input: [3,4,5,10] Expected: 22
Case 3
Input: [10,5,4,3] Expected: 10
Case 4
Input: [5] Expected: 5
View solutionHide solution3 approaches
1. Max Sum Increasing Subsequence
Time O(n²)Space O(n)
Like LIS but dp[i] carries the maximum SUM ending at i: dp[i] = a[i] + max(dp[j]) for j<i with a[j]<a[i].
function maxSumIS(a) { const dp = a.slice(); let best = dp[0] ?? 0; for (let i = 1; i < a.length; i++) { for (let j = 0; j < i; j++) if (a[j] < a[i]) dp[i] = Math.max(dp[i], dp[j] + a[i]); best = Math.max(best, dp[i]); } return best;}2. No three consecutive — pick-skip DP
Time O(n)Space O(1)
dp[i] = max(dp[i−1], dp[i−2] + a[i], dp[i−3] + a[i−1] + a[i]) — you may take one or two of any three in a row, never three.
function maxSumNoThreeConsecutive(a) { const n = a.length; if (n === 0) return 0; const dp = new Array(n).fill(0); dp[0] = a[0]; dp[1] = n > 1 ? a[0] + a[1] : dp[0]; for (let i = 2; i < n; i++) dp[i] = Math.max(dp[i - 1], dp[i - 2] + a[i], (i >= 3 ? dp[i - 3] : 0) + a[i - 1] + a[i]); return dp[n - 1];}3. Longest alternating subsequence & chain of pairs
Time O(n) / O(n log n)Space O(1)
Alternating: track two lengths — one ending on an "up" step, one on a "down" step. Chain of pairs: sort by second element, greedily extend when the next pair’s first exceeds the last chosen second (activity-selection style).
function longestAlternating(a) { let up = 1, down = 1; for (let i = 1; i < a.length; i++) { if (a[i] > a[i - 1]) up = down + 1; else if (a[i] < a[i - 1]) down = up + 1; } return Math.max(up, down);}function maxChainOfPairs(pairs) { pairs.sort((x, y) => x[1] - y[1]); let count = 0, lastEnd = -Infinity; for (const [a, b] of pairs) if (a > lastEnd) { count++; lastEnd = b; } return count;}Longest subsequence with adjacent difference one: dp keyed by value — dp[v] = 1 + max(dp[v−1], dp[v+1]) as you scan. Count subsequences with product < K: 2-D DP dp[i][p] over items and product thresholds. Max sum of pairs with difference exactly D: sort, two pointers, greedily pair.