Max Sum Increasing Subsequence

"""
Intuition:
The problem is similar to Longest Increasing Subsequence (LIS), but instead of
maximizing the length, we maximize the sum of the subsequence.

At every index i, we ask:
"What is the maximum sum of an increasing subsequence that MUST end at index i?"

To answer this, we look at all previous indices j < i:
- If arr[j] < arr[i], then arr[i] can extend the subsequence ending at j
- So we try: dp[j] + arr[i]
- We take the maximum among all such valid j

If no such j exists, then the subsequence contains only arr[i].

Solution Intuition:
- Define dp[i] = maximum sum of increasing subsequence ending at index i
- Initialize dp[i] = arr[i] (every element alone is a valid subsequence)
- For each i, iterate over all j < i:
    if arr[j] < arr[i]:
        dp[i] = max(dp[i], dp[j] + arr[i])
- Final answer is max(dp), since subsequence can end anywhere

Time Complexity: O(n^2)
Space Complexity: O(n)
"""

def fun(arr, i, dp):
    if dp[i] != -1:
        return dp[i]

    # Base: subsequence with only arr[i]
    dp[i] = arr[i]

    # Try extending previous subsequences
    for j in range(i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], fun(arr, j, dp) + arr[i])

    return dp[i]


class Solution:
    def maxSumIS(self, arr):
        n = len(arr)

        dp = [-1] * n

        ans = 0
        for i in range(n):
            ans = max(ans, fun(arr, i, dp))

        return ans