查找最大增加的最長子序列

Question

給定一個可以是正數和負數的數字序列，有幾種算法可以找到最長的遞增子序列。但是，如果有多個最長的子序列，有人能給我一個算法來找到最長和最長的子序列嗎？

示例：對於20，1,4，3，10，答案是1，4，10，而不是1，3，10

Answer 1

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 

Answer 2

這是一個動態規劃問題。這是一個工作示例。我試圖註釋代碼。但是，如果你最近沒有刷過動態編程概念，那麼很難理解這個解決方案。

解可以被認爲是

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); 
    } 
}