Geek asks and answers

Find the largest increasing subsequence with the maximum sum

Given a sequence of numbers that can be positive and negative, there are several algorithms for finding the longest growing subsequence. But can someone give me an algorithm to find the longest ascending subsequence with maximum sum if there are several longest ascending subsequences?

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

+3
source share
2 answers
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
+1
source

. . . , , .

S (j) = max {            , j (.. [j]),           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);
    }   
}
+1

More articles:


All Articles