求和最大的最长递增子序列

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结尾的最长求和子序列之和(即包含aj )，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);
    }   
}