大小为 4 的严格递增子序列的最大和

Question

有没有更有效的方法来获得大小为4的严格递增子序列的最大和？

我使用了 DP，其中 DP[i][j] = max(DP[k][j-1]) 使得 k < i 和 A[k] < A[i], j < 4，A 是数组。此解决方案的时间复杂度为 n^2.

我想降低时间复杂度。

令数组为 1, 10, 6, 8, 9, 11, 9, 9, 13 那么答案是 13 + 11 + 9 + 8

Answer 1

对于从 1 到 4 的每个 i，按降序排列最大值和总和，保留您已经找到的最佳选项。（您可以为此使用跳过列表、二叉树或其他任何东西。）这将严格按最大值和总和下降。

那么你的更新逻辑是这样的：

for i in [1, 2, 3, 4]:
    for j in your array:
        find for i-1 the best candidate whose max is < j:
        if found:
            create new candidate by adding j to that one
            look for best candidate of size i with max smaller than or equal to this
            if not found or its sum is < this one:
                insert new candidate into data structure
                delete from data structure any existing elements whose max >= this and whose sum is <= this.

每次查找都是O(log(n))。插入和删除也是。对于每个 i，对于每个元素，我们最多进行 2 次查找，1 次插入，稍后可能会进行删除。对于时间 O(k n log(n))，其中 k 是您正在寻找的递增链的长度。（在你的情况下，4。）

大小为 4 的严格递增子序列的最大和

Maximum sum of strictly increasing susequence of size 4

c

c++

arrays

algorithm

dynamic-programming