Home » Technical Interview Questions » Array Interview Questions » Maximum sum increasing subsequence

Maximum sum increasing subsequence


Reading Time - 3 mins

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;
}

READ  Queue Reconstruction by Height
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions