具有最大和加约束的最长递增子序列 - 可以跳过允许的元素数

Question

具有最大和（http://www.geeksforgeeks.org/dynamic-programming-set-14-maximum-sum-increasing-subsequence/）的最长递增子序列是一个经典的算法问题，并且网络上存在许多解决方案。但是，我只是遇到了这个问题的变体，不知道如何解决它。

与原始问题相比，现在还为您提供了一个数字m，该数字表示您最多可以从连续子范围中跳过的元素数，以便找到具有最大总和的LIS。例如，使用以下数组，

[1,200,300,3,4,5,6]

LIS 为 1，3，4，5，6，最大和为 19。但是，如果 m 为 1，则意味着在连续子范围内最多可以跳过一个元素以查找 LIS。因此，上述解决方案是不正确的，因为在 1 和 3 之间，跳过了两个元素（在本例中为 200，300）。新解决方案应为 3，4，5，6，因为在连续子范围内不会跳过任何元素。问题是找到具有最大和的LIS，并在给出数组和数字m时返回子序列（而不是子序列的总和或长度）。我已经坚持这个问题好几天了，所以任何帮助都是值得赞赏的。

编辑：O（n^2）解决方案现在已经足够好了，因为我完全不知道从哪里开始。

编辑：m是整个数组可以跳过的累积步骤，不是两个单独的递增子序列之间可以跳过的步骤。

Answer 1

这个问题可以通过使用动态编程技术来解决。

调用输入数组<代码>数据 长度<代码> n 。

假设我们有一个数组dp[n][n1]，其中条目dp[i][j]存储最接近的索引，从 dp[i][j]开始，递增子序列的长度从 i开始为 。如果我们有这个 dp，您的问题的结果是直接的。

现在，如何计算特定 j 的 dp[i][j]？将 i 从索引 n - 1 向后移动到 0，假设我们维护另一个数组列表[n 1]，list[i] 存储所有索引 k，其子序列从 k 和长度 i 开始递增。我们需要维护 list[j] 的属性：list[j] 是递减列表，元素位于索引 x，y 位于列表[j]中，则数据[x]

int[][]dp = new int[n][n + 1];
fill(dp, -1);
List<Integer>[]lists = new List[n + 1];
for(int i = n - 1; i >= 0; i--){
    for(int j = 1; j <= n; j++){
        if(j == 1){
            dp[i][j] = i;

        }else if(!list[j - 1].isEmpty()){
            int index = binary search in list[j - 1] to get the nearest index that greater than data[i];
            dp[i][j] = dp[index][j - 1];

        }
        if(dp[i][j] == -1)
           continue;
        while(data[list[j].peekLast()] <= data[i]){
        //Remove all entries which is smaller than i in list, we can easily see that all entries which is smaller than i can only end at point at least as near as end point of i.
           list[j].pollLast();
        }
        if(list[j].isEmpty() || dp[list[j].peekLast()][j] > dp[i][j]){
        //Only add entry to list if result of new entry is nearer. 
           list[j].add(i);
        }
    }
}

时间复杂度O(n^2。