Maximum sum increasing subsequence

Problem

Given an array of n positive integers. Find the sum of the maximum sum subsequence of the given array such that the integers in the subsequence are sorted in increasing order i.e. increasing subsequence.

Solution Approach

Expected Time complexity: $O(n^2)$

Click - to see solution code

C++

class Solution {
   public:
    int maxSumIS(int arr[], int n) {
        vector<int> dp(n);
        dp[0] = arr[0];
        int ans = arr[0];
        for (int i = 1; i < n; i++) {
            dp[i] = arr[i];
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = max(dp[i], dp[j] + arr[i]);
                }
                ans = max(ans, dp[i]);
            }
        }
        return ans;
    }
};