## Problem Statement

An array of positive integers of size `n`

is given. write a program to find the maximum sum increasing subsequence in the given array. The **maximum sum increasing subsequence** is a subsequence of an integer array where the sum is maximum and all of the elements are sorted in non decreasing order.

## Example

### Input-1

`arr[]: {1, 5, 2, 3, 9, 5}`

### Output-1

`15 `

### Explanation

Here, we have given an array of integers `1 5 2 3 9 5`

and the output should be $$1 + 2 + 3 + 9 = 15$$ because there are two subsequences exists that has a maximum sum of **15** i.e `1 5 9`

and `1 2 3 9`

, they are sorted as well in increasing order.

`arr[]: {1, 8, 3, 12, 2, 10, 4, 14, 2, 6, 6, 13, 2, 10}`

### Output-2

`35`

### Explanation

Here, we have given an array of integers `1 8 3 12 2 10 4 14 2 6 6 13 2 10`

and the output should be $1 + 8 + 12 + 14 = 35$ because there is one subsequence exists which has a maximum sum of 35 i.e `1 8 12 14`

, which is also sorted in increasing order.

## Constraints

```
0 <= n <= 20
0 <= n1, n2, .. <= 100
```

## Algorithm 1 – Naive Approach and algo-1: Using Recursion

### Intuition

Since this problem is a variation of the standard Longest Increasing Subsequence problem, hence we can use recursion to solve this problem. For each element in the given array, there are two cases:

- If the current element is greater than the previous element, include it.
- Else exclude the current element and use recursion for the remaining elements in the array.

### Algorithm

- Create a function that takes an
`arr[]`

array, a variable`i`

for indexing, a`prev`

variable to keep track of previous elements, and a sum`variable`

for calculating the maximum sum. - The base case here is when the
`arr[]`

is empty. - Check for two cases:
- Call the recursive function without the current element.
- If the element is greater than the previous element, call the recursive function for the current element.

- Finally, return the maximum sum of the above two cases.

### Code Implementation

**Code in C++**

```
// Naive Approach to find maximum sum increasing subsequence Using Recursion
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// Recursive function
int maximumSubsequence(vector<int> const &arr, int i, int prev, int sum){
// base case
if (i == arr.size()) {
return sum;
}
// If the element is greater than the previous element
int incl = sum;
if (arr[i] > prev) {
incl = maximumSubsequence(arr, i + 1, arr[i], sum + arr[i]);
}
// Call the recursive function without the current element.
int excl = maximumSubsequence(arr, i + 1, prev, sum);
// return the maximum of the above two choices
return max(incl, excl);
}
int main()
{
vector<int> arr = { 1, 8, 3, 12, 2, 10, 4, 14, 2, 6, 6, 13, 2, 10 };
cout << maximumSubsequence(arr, 0, INT_MIN, 0);
return 0;
}
```

**Code in Java**

```
// Naive Approach to find maximum sum increasing subsequence Using Recursion
class Main
{
// Recursive function
public static int maximumSubsequence(int[] arr, int i, int prev, int sum)
{
// base case: nothing is remaining
if (i == arr.length) {
return sum;
}
// If the element is greater than the previous element
int incl = sum;
if (arr[i] > prev) {
incl = maximumSubsequence(arr, i + 1, arr[i], sum + arr[i]);
}
// Call the recursive function without the current element.
int excl = maximumSubsequence(arr, i + 1, prev, sum);
// return the maximum
return Integer.max(incl, excl);
}
public static void main(String[] args)
{
int[] arr = { 1, 8, 3, 12, 2, 10, 4, 14, 2, 6, 6, 13, 2, 10 };
System.out.println(maximumSubsequence(arr, 0, Integer.MIN_VALUE, 0));
}
}
```

**Code in Python**

```
# Naive Approach to find maximum sum increasing subsequence Using Recursion
import sys
# Function to find the maximum sum of increasing subsequence
def maximumSubsequence(arr, i=0, prev=-sys.maxsize, total=0):
# base case: nothing is remaining
if i == len(arr):
return total
# case 1: exclude the current element and process the
# remaining elements
excl = maximumSubsequence(arr, i + 1, prev, total)
# case 2: include the current element if it is greater
# than the previous element
incl = total
if arr[i] > prev:
incl = maximumSubsequence(arr, i + 1, arr[i], total + arr[i])
# return the maximum of the above two choices
return max(incl, excl)
if __name__ == '__main__':
arr = [1, 8, 3, 12, 2, 10, 4, 14, 2, 6, 6, 13, 2, 10]
print(maximumSubsequence(arr))
```

#### Output

`35`

### Time Complexity

The time complexity is `O(nlogn)`

. Since we are going exponentially(not constant) not linearly (constant change) i.e in each iteration there are two cases to find maximum sum increasing subsequence, where n is the size of the given array.

### Space Complexity

The space complexity is `O(n)`

. Since recursion takes more space in the call stack to find maximum sum increasing subsequence.

## Algorithm 2 – Optimal Approach using DP and algo-2

### Intuition

The previous approach can be optimized by doing some slight changes in the Dynamic Programming approach to the Longest Increasing Subsequence problem. i.e replace the sum in place of the length of increasing subsequence.

We can also solve the problem in a **bottom-up approach**. If we draw the recursion tree for the above approach then we can easily see that there are some overlapping subproblems in the picture below, where substructure properties can be used easily.**In the bottom-up manner**, we first solve the smaller subproblems and then solve the larger subproblems from them.

### Algorithm

- arr[2] > arr[1] {MSIS[2] = max(MSIS [2], MSIS[1]+1 = 2}
- arr[3] < arr[1] {No change}
- arr[3] < arr[2] {No change}
- arr[4] > arr[1] {MSIS[4] = max(MSIS [4], MSIS[1]+1 = 2}
- arr[4] > arr[2] {MSIS[4] = max(MSIS [4], MSIS[2]+1 = 3}
- arr[4] > arr[3] {MSIS[4] = max(MSIS [4], MSIS[3]+1 = 3}

### Code Implementation

**Code in C++**

```
// Efficient Approach to find maximum sum increasing subsequence Using DP
#include <bits/stdc++.h>
using namespace std;
// function
int maximumSubsequence(int arr[], int n){
int i, j, max = 0;
int maximumSubsequence[n];
// Initialize maximumSubsequence values for all indexes
for ( i = 0; i < n; i++ )
maximumSubsequence[i] = arr[i];
// bottom up manner
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if (arr[i] > arr[j] &&
maximumSubsequence[i] < maximumSubsequence[j] + arr[i])
maximumSubsequence[i] = maximumSubsequence[j] + arr[i];
// Find maximum of all
for ( i = 0; i < n; i++ )
if ( max < maximumSubsequence[i] )
max = maximumSubsequence[i];
return max;
}
// Main method
int main(){
int arr[] = { 1, 8, 3, 12, 2, 10, 4, 14, 2, 6, 6, 13, 2, 10 };
int n = sizeof(arr)/sizeof(arr[0]);
cout << maximumSubsequence( arr, n ) << endl;
return 0;
}
```

**Code in Java**

```
// Efficient Approach to find maximum sum increasing subsequence Using DP
class Main{
// function
static int maximumSubsequence(int arr[], int n){
int i, j, max = 0;
int msis[] = new int[n];
// Initialize maximumSubsequence values for all indexes
for (i = 0; i < n; i++)
msis[i] = arr[i];
// bottom up manner
for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] &&
msis[i] < msis[j] + arr[i])
msis[i] = msis[j] + arr[i];
// Find maximum of all
for (i = 0; i < n; i++)
if (max < msis[i])
max = msis[i];
return max;
}
// Main method
public static void main(String args[]){
int arr[] = { 1, 8, 3, 12, 2, 10, 4, 14, 2, 6, 6, 13, 2, 10 };
int n = arr.length;
System.out.println(maximumSubsequence(arr, n));
}
}
```

**Code in Python**

```
# Efficient Approach to find maximum sum increasing subsequence Using DP
# function
def maximumSubsequence(arr, n):
max = 0
msis = [0 for x in range(n)]
# Initialize maximumSubsequence values for all indexes
for i in range(n):
msis[i] = arr[i]
# bottom up manner
for i in range(1, n):
for j in range(i):
if (arr[i] > arr[j] and
msis[i] < msis[j] + arr[i]):
msis[i] = msis[j] + arr[i]
# Find maximum of all
for i in range(n):
if max < msis[i]:
max = msis[i]
return max
# Driver Code
arr = [1, 8, 3, 12, 2, 10, 4, 14, 2, 6, 6, 13, 2, 10]
n = len(arr)
print(str(maximumSubsequence(arr, n)))
```

**Output**

`35`

### Time Complexity

The time complexity is `O(n^2^)`

. Since we are using two nested for loops and traversing the array `n`

^2^ times in to find the maximum sum increasing subsequence, where `n`

is the size of the given array.

### Space Complexity

The space complexity is `O(n)`

. Since we are using an extra array to store MSIS values at each index in the Program to find maximum sum increasing subsequence.

## Conclusion

- We have given an array of positive integers of size n is given. write a program to find the maximum sum increasing subsequence in the given array.
- The maximum sum increasing subsequence is a subsequence of an integer array where the sum is maximum and all of the elements are sorted in non-decreasing order.
- For eg, an array
`{1, 8, 3, 12, 2, 10, 4, 14, 2, 6, 6, 13, 2, 10}`

is given, here the output should be`1 + 8 + 12 + 14 = 35`

. - Since this problem is a variation of the standard Longest Increasing Subsequence problem, hence we can use recursion and DP to solve this problem with a slight change.
- The naive approach takes
`O(nlogn)`

time complexity as we are going exponentially not linearly, and`O(n)`

space complexity because of the call stack. - On the other hand, the efficient approach to Find maximum sum increasing subsequence takes
`O(n^2^)`

time complexity and`O(n)`

as a space complexity as we are using an extra array.

## FAQ

Q.**Why dynaminc programming is the efficient approach?**

A. DP is the most efficient approach for maximum sum increasing subsequence because Dynamic programming solves the problem with optimal substructure and overlapping subproblems as DP memorizes subproblem solutions rather than repeatedly computing them.

Q.**What is the bottom-up approach?**

A. In the bottom-up manner, we first solve the smaller subproblems and then solve the larger subproblems from them.

Q.**What are some similar coding questions on Dynamic programming?**

A. Refer Longest Increasing Subsequence problem

Refer Coin Change Problem

Refer Climbing Stairs Problem