查找具有最大总和的最长递增子序列 [英] Find the Longest Increasing Subsequence with the Maximum Sum

问题描述

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

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

这篇关于查找具有最大总和的最长递增子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！