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


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

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


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;
	int max=msis[0];
	for (int i = 0; i < n; ++i) //finding the maximum value
	cout<<"Value of Maximum sum increasing subsequence is: "<<max;

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

Leave a Comment

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions