查找具有最大总和的最长递增子序列

本文介绍了查找具有最大总和的最长递增子序列的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给定一个可以为正和负的数字序列，有几种算法可以找到最长的递增子序列。但是，如果存在多个最长增长的子序列，有人可以给我一种算法来找到最长的增长最大的子序列吗？

Given a sequence of number which can be positive and negative, there are several algorithms to find the longest increasing subsequence. But can someone give me an algorithm to find the longest increasing subsequence with the maximum sum if there are multiple longest increasing subsequences?

例如：对于20、1、4、3、10，答案是1、4、10，而不是1、3、10

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

推荐答案

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