Subsequence DP — max sum increasing, longest with adjacent diff one, no three consecutive, alternating, product < K, chain of pairs

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.