Given an array of integers, find the maximum sum of an increasing subsequence. For [1, 101, 2, 3, 100, 4, 5], the answer is 106 because the subsequence [1, 2, 3, 100] has sum , which beats [1, 2, 3, 4, 5] with sum 15.
This is LIS where you get the highest sum instead of length. The longest subsequence isn't always the best. Read the problem statement carefully, noting the constraints. Try to identify the recursive structure before looking at the solution.