最大合計で最大増加サブシーケンスを見つける

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）=最大{Jで終わる最長の和サブシーケンスの 合計（すなわち、A [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); 
    } 
}