大小为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，通过递减最大值和求和来保持您已经找到的最佳选项。(您可以使用skiplist、二叉树或其他任何方法。(这将严格按照最大AND和递减。

然后你的更新逻辑看起来是这样的：

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。(