Maximum sum increasing subsequence, gfg

Statement -

Given an array arr of N positive integers, the task is to find the maximum sum increasing sub-sequence of the given array.

Example 1:

Input: N = 5, arr[] = {1, 104, 2, 3, 100} 
Output: 106

Explanation:The maximum sum of a
increasing sequence is obtained from
{1, 2, 3, 100}

Solution - It's same as LIS. In LIS we initialize dp's elements to 1, but here copy all array's elements into dp. 

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