# Maximum Sum Increasing Subsequence

## Maximum Sum Increasing Subsequence

The maximum sum incresasing subsequence is a variation of the very famous problem – Longest Increasing subsequence. In this article we provide a C++ solution with explanation of the problem.

## Maximum Sum Increasing Subsequence Problem Description

Given an array of n integers, output the maximum sum of an increasing subsequence ie the sequence should be increasing and out of all increasing subsequences output the maximum possible sum.

Input:

• First-line contains integer n – the length of the array.
• The next line contains n integers.

Output:

• Single Integer, the required sum.

Example:

Input:

• 4
• 1 3 1 100

Output:

• 104 {1+ 3 + 100}

Possible subsequences are –

• 1, 100 with sum = 101
• 1, 3, 100 with sum = 104
• 3, 100 with sum = 103
• 1 with sum = 1
• 3 with sum = 3
• 100 with sum = 100

104 is the maximum sum and thus the answer.

## Solution Explanation

This problem is a variation of longest increasing subsequence problem.

In LIS we use dp[] array and store the length of increasing susequence ending at i. In this problem instead of length we will store sum of subsequence.

Time Complexity – The time complexity is O(n^2) as we used two nested array to compute the sum.

Space Complexity – The space complexity is O(n) as we use only one auxiliary array to store the result.

### Code

#include <bits/stdc++.h>
using namespace std;
int f(int arr[], int n)
{
int dp[n];
// Dp array to store msi subsequence ending at i

int ans = INT_MIN;
for (int i = 0i < ni++)
{
dp[i] = arr[i];
for (int j = 0j < ij++)
{
if (arr[j] <= arr[i]) // as j arr[i] can extend
{                     // msi subsequence ending at j
dp[i] = max(dp[i], arr[i] + dp[j]);
}
}
// Checking max sum of all i
ans = max(ansdp[i]);
}

return ans;
}
int main()
{
int n;
cin >> n;
int arr[n];
for (int i = 0i < ni++)
cin >> arr[i];

cout << f(arrn<< endl;
return 0;
}

### Output

`33 1 100103`