Find the Longest Increasing Subsequence with the Maximum Sum

Question

Given a sequence of number which can be positive and negative, there are several algorithms to find the longest increasing subsequence. But can someone give me an algorithm to find the longest increasing subsequence with the maximum sum if there are multiple longest increasing subsequences?

Example: For 20, 1, 4, 3, 10, the answer is 1, 4, 10, not 1, 3, 10

What do you do if there is a conflict between longest and maximum sum? 1,2,3,10,4,5 => sum (1,2,3,10) > sum (1,2,3,4,5) but the second is longer. — user unknown, Apr 14 '12 at 19:15

score 3 · Accepted Answer · answered Apr 14 '12 at 20:58

dpLen[i] = maximum length of a LIS with maximum sum ending at i
dpSum[i] = maximum sum of a LIS with maximum sum ending at i

for i = 0 to n do
  dpLen[i] = 1
  dpSum[i] = input[i]

  maxLen = 0
  for j = 0 to i do
    if dpLen[j] > maxLen and input[j] < input[i]
      maxLen = dpLen[j]

  for j = 0 to i do
    if dpLen[j] == maxLen and input[j] < input[i] and dpSum[j] + input[i] > dpSum[i]
      dpSum[i] = dpSum[j] + input[i]

  dpLen[i] = maxLen + 1

snegi · Answer 2 · 2013-10-24T21:47:57.980

This is a dynamic programming problem. Here is a working example. I have tried to annotate the code. But again if you have not recently brushed up Dynamic programming concepts, it will be hard to understand the solution.

Solution can be thought of as

S(j) = max { Sum of longest sum sub-sequence ending at j (i.e a[j] is included), S(j-1) }

public class LongestSumSequence{

    public static void printLongestSumSubsequence(int[] seq) {
        int[] S = new int[seq.length];

        //S[j] contains the longest sum of subsequence a1,a2,a3,....,aj
        //So a sub sequence with length 1 will only contain first element.
        //Hence we initialize it like this
        S[0] = seq[0];
        int min_index = 0;
        int max_index = 0;

        //Now like any dynamic problem we proceed by solving sub problems and 
        //using results of subproblems to calculate bigger problems
        for(int i = 1; i < seq.length; i++) {

            //Finding longest sum sub-sequence ending at j
            int max = seq[i];
            int idx = i;
            int sum = seq[i];
            for(int j = i-1; j >=0 ; j--) {
                sum += seq[j];  
                if(max < sum) { 
                    idx = j;            
                    max = sum;          
                }               
            }
            //Now we know the longest sum subsequence ending at j, lets see if its
            //sum is bigger than S(i-1) or less
            //This element is part of longest sum subsequence
            if(max > S[i-1]) {
                S[i] = max;     
                max_index = i;  
                min_index = idx;
            } else {    
                //This element is not part of longest sum subsequence
                S[i] = S[i-1];  
            }           
        }       

        System.out.println("Biggest Sum : "+S[seq.length - 1]);
        //Print the sequence
        for(int idx = min_index; idx <= max_index; idx++) {
            System.out.println("Index " + idx +  "Element " + seq[idx]);
        }       
    }   

    public static void main(String[] args) {
        int[] seq = {5,15,-30,10,-5,40,10};
        printLongestSumSubsequence(seq);
    }   
}

Find the Longest Increasing Subsequence with the Maximum Sum

2 Answers2

Linked