Maximum sum increasing subsequence

Given an array, this function will find the sum of maximum subsequence of the given array, that is the integers in the subsequence are in sorted order.

A subsequence is a part of an array which is a sequence that is derived from another sequence by deleting some elements without changing the order. This can be explained in below example

Example

INPUT:
arr[] = {18, 5, 17, 23}

OUTPUT:
45
In the above example, 45 is the maximum sum. In the above example, there are two increasing subsequences ie, {18, 17} and {5, 17, 23}. But the second subsequence has the maximum sum

Time Complexity: O( )

In this method, we will be using recursion

Algorithm

1. Create a new array and initialize the array elements ie, msis[] = arr[]

2. Simply run two loops

3. In the outer loop pick each element in the array ie, i=0 to size(n)

4. In the inner loop, select each element from 0th to i th index ie, j= 0 to i

5. If arr[j] < arr[i] and msis[i] < msis[j] + arr[i], then msis[i] = msis[j] + arr[i]

6. find the maximum in msis[] array and print the value.

C++ Program

#include <bits/stdc++.h>
using namespace std;

void maxSumIncSubSeq(int arr[],int n)
{
	int msis[n];
	for (int i = 0; i < n; ++i) //Initializing the values of msis[]
	{
		msis[i] = arr[i];
	}

	for (int i = 0; i < n; ++i) //recursion, storing the inc subsequnce sums in msis[] array
	{
		for (int j = 0; j < i; ++j)
		{
			if(arr[j]<arr[i] && msis[i]<msis[j]+arr[i])
			{
				cout<<msis[i]<<" "<<msis[j]+arr[i]<<endl;
				msis[i]=msis[j]+arr[i];
			}
		}
	}
	int max=msis[0];
	for (int i = 0; i < n; ++i) //finding the maximum value
	{
		if(max<msis[i])
		{
			max=msis[i];
		}
	}
	cout<<"Value of Maximum sum increasing subsequence is: "<<max;
}

int main() {
   int arr[]={18, 5, 17, 23};
   int n=sizeof(arr)/sizeof(arr[0]);
   
   maxSumIncSubSeq(arr,n);
   return 0;
}