algorithm - Mdoify LIS 使得一个元素大于之前所有元素的总和

Question

假设一个数组 = {2,5,7,8,10}。您需要找到最长递增子序列的长度，使得一个元素不小于其之前所有元素的总和。

在这种情况下，答案可以是 {2,5,7}、{2,5,8} 或 {2,8,10}。所以 Length = 3
这在 O(n^2) 中很容易解决。因为 LIS 长度可以在 O(n log n) 中找到。由于问题只问长度，所以我认为这个问题也可以在 O(n log n) 中解决。但我该怎么做呢？

Answer 1

1. 有一个O(N^2)动态编程解决方案，如下所示：

   • 设为以第一个元素之一结尾并由精确元素组成的f(i, j) “正确”子序列可以具有的最小总和。ij

   • 基本情况是f(0, 0) = 0（空前缀，无元素）

   • 转换是f(i, j) -> f(i + 1, j)（不添加新元素）和
     f(i, j) -> f(i + 1, j + 1) if a[i] > f(i, j)（i如果可以的话，将第 - 个元素添加到子序列的末尾）。

这个方案的正确性不言而喻。

2. 一个很酷的事实：让我们A成为k元素的“正确”子序列。比 的最后一个元素A不小于max(1, 2^(k-2))（证明：k = 1和的情况k = 2。现在我们可以使用归纳法和事实1 + sum i = 0 .. k of 2^k = 2^(k+1)）

3. 因此，j范围0..log MAX_A + C在上述动态规划解决方案中，因此它适用于O(N * log MAX_A).

O(N * log MAX_A)不是O(N log N)，但这个解决方案可以很好地用于实际目的。

Answer 2

实际上，您根本不需要 DP 解决方案。
首先按非降序对数字进行排序。并从左到右循环。跟踪当前总和。
如果下一个数字不小于总和，则将其添加到 LIS。否则继续下一个数字。
可以证明贪心解是最优解。自己证明；）