Найдите самую длинную возрастающую подпоследовательность с максимальной суммой

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 (то есть 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);
    }   
}