Given an array of n positive integers. Write a program to find the sum of maximum sum subsequence of the given array such that the integers in the subsequence are sorted in increasing order.

For example, if input is {1, 101, 2, 3, 100, 4, 5}, then output should be 106 (1 + 2 + 3 + 100), if the input array is {3, 4, 5, 10}, then output should be 22 (3 + 4 + 5 + 10) and if the input array is {10, 5, 4, 3}, then output should be 10

Solution:

This problem is a variation of standard Longest Increasing Subsequence (LIS) problem. We need a slight change in the Dynamic Programming solution of LIS problem. All we need to change is to use sum as a criteria instead of length of increasing subsequence.

Longest increasing subsequence

Longest increasing subsequence

Java implementation:

Java 
class MSIS
{

  
    static int maxSumIS( int arr[], int n )
    {
        int i, j, max = 0;
        int msis[] = new int[n];
 
        
        for ( i = 0; i < n; i++ )
            msis[i] = arr[i];
 
        
        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];
 
       
        for ( i = 0; i < n; i++ )
            if ( max < msis[i] )
                max = msis[i];
 
        return max;
    }
 

    public static void main(String args[])
    {
        int arr[] = new int[]{1, 101, 2, 3, 100, 4, 5};
        int n = arr.length;
        System.out.println("Sum of maximum sum increasing "+
                           " subsequence is "+
        maxSumIS( arr, n ) );
    }
}

Output:

Sum of maximum sum increasing subsequence is 106

Time Complexity: O(n^2)

[ad type=”banner”]

Categorized in:

AlgorithmCodingDynamic ProgrammingJAVA

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , ,