Skip to main content

Maximum Sum Increasing Subsequence

Learn Maximum Sum Increasing Subsequence (Dynamic Programming, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Maximize SUM Instead of LENGTH Same O(n&sup2;) LIS shape, but dp[i] tracks the maximum SUM of an increasing subsequence ending at i, not its length: dp[i] = arr[i] + max(dp[j]) for every valid j < i with arr[j] < arr[i] .

More lessons in Dynamic Programming