Maximum Sum Increasing Subsequence

Difficulty Level Easy
Frequently asked in Amazon Fanatics Microsoft Morgan Stanley
Array Dynamic ProgrammingViews 1941

Problem Statement

You are given an array of integers. Your task is to find out the maximum sum subsequence within the array in such a way that the numbers in subsequence should be ordered in a sorted manner in increasing order. A subsequence is nothing but a sequence that we get if we remove some of the elements from the initial array.

Example

arr[] = {2,4,5,10,1,12}
33

Explanation: Sum of {2, 4, 5, 10, 12} ⇒ 33. We have taken the whole initial input array except the element at index 4(0-based indexing) to satisfy our sorted condition. This subsequence gives us the best result. Any other subsequence will result in a sum less than the current sum.

arr[] = {3,5,7,1,20,4,12}
35

Explanation: Sum of {3, 5, 7, 20} ⇒ 35. Here, we have removed 1 and 4 which makes the rest of the array sorted. Then the remaining elements make maximum sum increasing subsequence.

 

Algorithm for Maximum Sum Increasing Subsequence

1. Declare an array say maxSumIS as the same size as the length of an array.
2. Set the output to 0.
3. Copy each element of an array into the created array.
4. Traverse the array from i=1 to i<n(length of the array)
  Now in another loop, from j=0 to j<i,
    Check if arr[i] is greater than arr[j] and maxSumIS[i] is less than maxSumIS[j]+arr[i]N,
      Then update the value of maxSumIS[i] = maxSumIS[j] + arr[i].
5. Traverse the array, and find out the maximum of all the elements from maxSumIS and return that value.

 

Explanation

We have given an array of integers that may or may not be sorted. We try to find the maximum sum increasing subsequence. That should be in increasing order as well. So, we will create an array for that, with the same size as of the given array. Then we set the output to 0. This output value will be helping us in finding a maximum among all elements.

We will traverse the array for the first time. The first time will be for copying the value of a given array into an array we created maxSumIS[]. This maxSumIS[] array is updated whenever our condition is satisfied. So we will first traverse the array from i=1 because we are going to use the first index in maxSumIS array. That’s why we have just taken the value for the second loop from 0 to i. We are going to check the condition if arr[i] is greater than the arr[j], and also maxSumIS[j] is less than the sum of the previous two elements according to the current indices i and j. If both conditions are satisfied then we update the value of maxSumIS[i] to the sum of the current two indices’ element as maxSumIS[j] and arr[i].

This is because we want to find the subsequence of the maximum sum in increasing order only, that’s why we are taking two elements simultaneously.

After this, we have to find out the maximum of all the elements we stored and updated in an array maxSumIS. We can traverse the whole array or we can find the maximum number using any function. But we need to return the maximum number among all the elements of the array maxSumIS.

Maximum Sum Increasing Subsequence

Code for Maximum Sum Increasing Subsequence

C++ Code

#include<iostream>
using namespace std;

int getMaximumSumIS(int arr[], int n)
{
    int i, j, output = 0;
    int maxSumIS[n];

    for ( i = 0; i < n; i++ )
        maxSumIS[i] = arr[i];

    for ( i = 1; i < n; i++ )
        for ( j = 0; j < i; j++ )
            if (arr[i] > arr[j] && maxSumIS[i] < maxSumIS[j] + arr[i])
                maxSumIS[i] = maxSumIS[j] + arr[i];

    // Take the maximum out of all the possible answers
    for ( i = 0; i < n; i++ )
        if ( output < maxSumIS[i] )
            output = maxSumIS[i];

    return output;
}
int main()
{
    int arr[] = {2,4,5,10,1,12};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Total sum of Maximum Sum Increasing Subsequence : " << getMaximumSumIS( arr, n );
    return 0;
}
Total sum of Maximum Sum Increasing Subsequence : 33

 

Java Code

class MaximumSumIncreasingsubsequence
{
    public static int getMaximumSumIS(int arr[], int n)
    {
        int i, j, output = 0;
        int maxSumIS[] = new int[n];

        for (i = 0; i < n; i++)
            maxSumIS[i] = arr[i];

        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (arr[i] > arr[j] && maxSumIS[i] < maxSumIS[j] + arr[i])
                    maxSumIS[i] = maxSumIS[j] + arr[i];

        // Take the maximum out of all the possible answers
        for (i = 0; i < n; i++)
            if (output < maxSumIS[i])
                output = maxSumIS[i];

        return output;
    }
    public static void main(String args[])
    {
        int arr[] = {2,4,5,10,1,12};
        int n = arr.length;
        System.out.println("Total sum of Maximum Sum Increasing Subsequence : "+getMaximumSumIS(arr, n));
    }
}

Total sum of Maximum Sum Increasing Subsequence : 33

 

Complexity Analysis

Time Complexity

Since here we have two nested loops outer loop from 0 to n-1 and inner loop from 0 to i. Thus algorithm has polynomial time complexity. O(n2) where “n” is the number of elements in the array.

Space Complexity

Here, we have only 1D arrays of size n contributing linear space complexity to the problem. O(n) where “n” is the number of elements in the array.

Translate »