Master the Maximum Sum Increasing Subsequence Problem (DP-14): A Comprehensive Guide

Struggling with dynamic programming problems? This guide breaks down the "Maximum Sum Increasing Subsequence" problem (MSIS), a classic challenge with practical applications in data analysis and algorithm design. You'll learn how to find the subsequence with the largest sum from a given array, ensuring the elements are in increasing order. Let's dive in!

What is the Maximum Sum Increasing Subsequence?

It's about identifying a subset of numbers within a larger array that meet two crucial conditions:

Increasing Order: The numbers in the subset must be arranged from smallest to largest.
Maximum Sum: The sum of these numbers must be the highest possible compared to all other increasing subsequences within the array.

For example, in the array {1, 101, 2, 3, 100, 4, 5}, the Maximum Sum Increasing Subsequence is {1, 2, 3, 100}, and its sum is 106.

Why is MSIS important?

Understanding MSIS helps with:

Optimizing Solutions: Finding the most efficient way to achieve a goal when dealing with ordered data.
Algorithmic Thinking: Enhancing your problem-solving skills using dynamic programming.
Real-World Applications: Applicable in finance (analyzing stock trends), bioinformatics (analyzing gene sequences), and more.

Breaking Down the Problem

The core idea is to adapt the well-known Longest Increasing Subsequence (LIS) dynamic programming approach. Instead of focusing on the length of the increasing subsequence, we prioritize the sum.

Dynamic Programming Approach: The Step-by-Step Solution

We'll use an array msis[] to store the maximum sum of increasing subsequences ending at each index of the input array.

Initialization: Initially, each msis[i] is set to arr[i] because a single element is an increasing subsequence of itself.
Iteration: We iterate through the array, and for each element arr[i], we check all preceding elements arr[j] (where j < i).
Condition Check: If arr[i] > arr[j] (ensuring the increasing order) and msis[i] < msis[j] + arr[i] (checking if adding arr[i] to the subsequence ending at arr[j] increases the sum), we update msis[i] to msis[j] + arr[i].
Maximization: After the iterations, we find the maximum value in the msis[] array, which represents the sum of the Maximum Sum Increasing Subsequence.

Code Examples in Multiple Languages

Below you can find implementations of the algorithm in various popular programming languages.

C++ Implementation:

/* Dynamic Programming implementation
 of Maximum Sum Increasing Subsequence
 (MSIS) problem */
#include <iostream>
using namespace std;

/* maxSumIS() returns the maximum
sum of increasing subsequence
in arr[] of size n */
int maxSumIS(int arr[], int n)
{
    int i, j, max = 0;
    int msis[n];

    /* Initialize msis values
    for all indexes */
    for ( i = 0; i < n; i++ )
        msis[i] = arr[i];

    /* Compute maximum sum values
    in bottom up manner */
    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];

    /* Pick maximum of
    all msis values */
    for ( i = 0; i < n; i++ )
        if ( max < msis[i] )
            max = msis[i];

    return max;
}

// Driver Code
int main()
{
    int arr[] = {1, 101, 2, 3, 100, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Sum of maximum sum increasing "
            "subsequence is " << maxSumIS( arr, n ) << endl;
    return 0;
}
// This is code is contributed by rathbhupendra

C Implementation:

/* Dynamic Programming implementation
of Maximum Sum Increasing Subsequence
(MSIS) problem */
#include <stdio.h>

/* maxSumIS() returns the maximum
    sum of increasing subsequence
    in arr[] of size n */
int maxSumIS(int arr[], int n)
{
    int i, j, max = 0;
    int msis[n];

    /* Initialize msis values
        for all indexes */
    for( i = 0; i < n; i++ )
        msis[i] = arr[i];

    /* Compute maximum sum values
        in bottom up manner */
    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];

    /* Pick maximum of
        all msis values */
    for( i = 0; i < n; i++ )
        if( max < msis[i] )
            max = msis[i];

    return max;
}

// Driver Code
int main()
{
    int arr[] = {1, 101, 2, 3, 100, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Sum of maximum sum increasing "
            "subsequence is %d\n",
            maxSumIS( arr, n ) );
    return 0;
}

Java Implementation:

/* Dynamic Programming Java
    implementation of Maximum Sum
    Increasing Subsequence (MSIS)
    problem */
class GFG
{
    /* maxSumIS() returns the
        maximum sum of increasing
        subsequence in arr[] of size n */
    static int maxSumIS(int arr[], int n)
    {
        int i, j, max = 0;
        int msis[] = new int[n];

        /* Initialize msis values
            for all indexes */
        for (i = 0; i < n; i++)
            msis[i] = arr[i];

        /* Compute maximum sum values
            in bottom up manner */
        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];

        /* Pick maximum of all
            msis values */
        for (i = 0; i < n; i++)
            if (max < msis[i])
                max = msis[i];

        return max;
    }

    // Driver code
    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));
    }
}

// This code is contributed
// by Rajat Mishra

Python3 Implementation:

# Dynamic Programming based Python
# implementation of Maximum Sum
# Increasing Subsequence (MSIS)
# problem

# maxSumIS() returns the maximum
# sum of increasing subsequence
# in arr[] of size n
def maxSumIS(arr, n):
    max_so_far = 0
    msis = [0 for x in range(n)]

    # Initialize msis values
    # for all indexes
    for i in range(n):
        msis[i] = arr[i]

    # Compute maximum sum
    # values in bottom up manner
    for i in range(1, n):
        for j in range(i):
            if (arr[i] > arr[j] and
                    msis[i] < msis[j] + arr[i]):
                msis[i] = msis[j] + arr[i]

    # Pick maximum of
    # all msis values
    for i in range(n):
        if max_so_far < msis[i]:
            max_so_far = msis[i]

    return max_so_far

# Driver Code
arr = [1, 101, 2, 3, 100, 4, 5]
n = len(arr)
print("Sum of maximum sum increasing " +
            "subsequence is " +
            str(maxSumIS(arr, n)))

# This code is contributed
# by Bhavya Jain

C# Implementation:

// Dynamic Programming C# implementation
// of Maximum Sum Increasing Subsequence
// (MSIS) problem
using System;
class GFG {

    // maxSumIS() returns the
    // maximum sum of increasing
    // subsequence in arr[] of size n
    static int maxSumIS( int []arr, int n )
    {
        int i, j, max = 0;
        int []msis = new int[n];

        /* Initialize msis values
            for all indexes */
        for( i = 0; i < n; i++ )
            msis[i] = arr[i];

        /* Compute maximum sum values
            in bottom up manner */
        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];

        /* Pick maximum of all
            msis values */
        for( i = 0; i < n; i++ )
            if( max < msis[i] )
                max = msis[i];

        return max;
    }

    // Driver Code
    public static void Main()
    {
        int []arr = new int[]{1, 101, 2, 3, 100, 4, 5};
        int n = arr.Length;
        Console.WriteLine("Sum of maximum sum increasing " +
                            " subsequence is " +
                            maxSumIS(arr, n));
    }
}

// This code is contributed by Sam007

PHP Implementation:

<?php
// Dynamic Programming implementation
// of Maximum Sum Increasing
// Subsequence (MSIS) problem

// maxSumIS() returns the maximum
// sum of increasing subsequence
// in arr[] of size n
function maxSumIS($arr , $n )
{
    $max = 0;
    $msis = array($n);

    // Initialize msis values
    // for all indexes
    for( $i = 0; $i < $n; $i++ )
        $msis[$i] = $arr[$i];

    // Compute maximum sum values
    // in bottom up manner
    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];

    // Pick maximum of all msis values
    for( $i = 0; $i < $n; $i++ )
        if( $max < $msis[$i] )
            $max = $msis[$i];

    return $max ;
}

    // Driver Code
    $arr = array(1, 101, 2, 3, 100, 4, 5);
    $n = count($arr);
    echo "Sum of maximum sum increasing subsequence is ".maxSumIS( $arr , $n);
        
// This code is contributed by Sam007
?>

Javascript Implementation:

    
// Dynamic Programming implementation
// of Maximum Sum Increasing Subsequence
// (MSIS) problem

// maxSumIS() returns the maximum
// sum of increasing subsequence
// in arr[] of size n
function maxSumIS(arr, n)
{
    let i, j, max = 0;
    let msis = new Array(n);

    // Initialize msis values
    // for all indexes
    for(i = 0; i < n; i++)
        msis[i] = arr[i];

    // Compute maximum sum values
    // in bottom up manner
    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];

    // Pick maximum of
    // all msis values
    for(i = 0; i < n; i++)
        if(max < msis[i])
            max = msis[i];

    return max;
}

// Driver Code
let arr = [ 1, 101, 2, 3, 100, 4, 5 ];
let n = arr.length;
document.write("Sum of maximum sum increasing "+
        "subsequence is "+ maxSumIS(arr, n));
                    
// This code is contributed by rishavmahato348

Complexity Analysis

Time Complexity: O(n^2) due to the nested loops for iteration.
Space Complexity: O(n) for the msis[] array.

Key Takeaways

The Maximum Sum Increasing Subsequence problem combines dynamic programming with subsequence analysis.
Understanding the LIS problem provides a strong foundation for tackling MSIS.
The dynamic programming approach allows for efficient computation of the maximum sum.

Next Steps

Now that you understand the Maximum Sum Increasing Subsequence, challenge yourself with these related problems:

Longest Increasing Subsequence (LIS)
Maximum Sum Decreasing Subsequence
Variations involving constraints on subsequence length or elements

By mastering these concepts, you'll significantly strengthen your dynamic programming skills and be well-equipped to solve a wide range of algorithmic challenges!