311. Maximum Sum Increasing Subsequence

Given an array of n integers, find the maximum possible sum of the elements of a strictly increasing subsequence.

Input: Two lines: the first contains n, the second contains n space-separated integers. Output: Print a single integer - the maximum sum of a strictly increasing subsequence.

1 <= n <= 10^4

Just like standard LIS, the answer is the MAXIMUM across the WHOLE dp array, not just its last entry - the best-summing increasing run doesn't have to end at the array's final element.

Find the maximum possible SUM (not just length) of a strictly increasing subsequence. Brute force: Try every possible increasing subsequence directly and sum each, taking the maximum - this is exponential, impractical for n up to 10^4. Optimised: This is the exact same DP shape as Longest Increasing Subsequence, just replacing 'add 1 for length' with 'add arr[i] for sum' - the compatibility check (arr[j]<arr[i]) and the overall structure are identical, only the accumulated quantity differs.

Compress the array's values to ranks, then process elements left to right while maintaining a Binary Indexed Tree (Fenwick tree) that supports a prefix-maximum query: for each element, query the best achievable increasing-subsequence sum among all smaller values in O(log n), add the current element's value to get its own dp value, and update the tree at this element's rank with that value. This replaces the O(n^2) DP's linear scan over all earlier indices with a logarithmic tree query, cutting the total time down to O(n log n) while still computing the exact same dp values as the previous approach. Time: O(n log n) Space: O(n)

Define dp[i] as the maximum sum of a strictly increasing subsequence that ends exactly at index i, computed as arr[i] plus the best dp[j] among all earlier indices j with arr[j] < arr[i] (or just arr[i] alone if no such j exists). Filling this array left to right and taking the maximum over all dp[i] at the end gives the answer, reusing previously solved subproblems instead of re-deriving whole subsequences from scratch. This reduces the exponential brute-force search to a polynomial one, though it still checks all earlier indices for every position. Time: O(n^2) Space: O(n)

Generate every one of the 2^n possible subsequences of the array, check which ones are strictly increasing, and track the maximum total sum among those that qualify. This is guaranteed to find the true answer since it considers every possible subsequence, but the exponential blow-up makes it impractical for anything beyond very small arrays. Time: O(2^n) Space: O(n)

1. dp[i] = the maximum sum of an increasing subsequence ENDING exactly at index i; initialize dp[i]=arr[i] for every i. 2. For each i, look at every earlier index j with arr[j]<arr[i], and update dp[i]=max(dp[i], dp[j]+arr[i]). 3. The answer is the MAXIMUM value anywhere in the dp array, not necessarily dp[n-1].

Time: O(n²) - for each index i, checking all earlier indices j. Space: O(n), for the dp array.

Test n = 1 (answer is that single element), a strictly decreasing array (best subsequence is just its single largest element), and n = 10^4 for the O(n^2) DP's performance.

Be ready to immediately connect this to standard LIS - recognizing 'this is LIS but summing values instead of counting length' is exactly the kind of quick pattern-transfer that shows deep understanding rather than memorized solutions.