Weighing the chain, not counting its links
Same increasing-chain table, but each step adds a value instead of adding one. About 12 minutes.
Heaviest instead of longest
Now each rising chain is worth the sum of its numbers, and you want the most valuable one. Picture stacking boxes where each box must be bigger than the one before, and you want the tallest stack by weight, not by count.
Only the arithmetic changes. You still look back at every earlier, smaller number. But instead of "one more link", a chain ending here is worth this number plus the best sum of the chain it extends.
Longest isn't always heaviest
In 1, 101, 2, 3, 100, 4, 5, the longest rising chain is 1, 2, 3, 4, 5, worth 15. But 1, 2, 3, 100 is worth 106. A few big numbers beat many small ones.
As before, the answer is the biggest value anywhere in the row. And a number can always start fresh on its own, which the rule handles automatically.
best = nums[:] # each alone has its own value
1 alone is 1. 101 follows 1: 102.
The number here is 100. The best rising chain before it, using only smaller numbers, is worth 3. What's the best chain ending on the 100 worth?
- A103
- B100
- C3
Show the answer
103. Extend that chain with the 100: 3 + 100 = 103.
Maximum sum increasing subsequence
Given an array of integers nums, return the largest possible sum of a strictly increasing subsequence — values in the same order as nums, each strictly greater than the one before, summed together.
nums = [1, 101, 2, 3, 100, 4, 5] → 106
0 ≤ n ≤ 1,000 · −1,000,000,000 ≤ each value ≤ 1,000,000,000