修改 LIST 使得一个元素大于之前所有元素的总和
Mdoify LIS Such that a element is greater than sum of all elements before
Suppose an array = {2,5,7,8,10}. You need to find the length of Longest Increasing Sub-sequence such that a element is not less than the sum of all elements before it.
在这种情况下，答案可以是 {2,5,7}、{2,5,8} 或 {2,8,10}。所以长度 = 3
这在 O(n^2) 中很容易解决。由于 LIS 长度可以在 O(n log n) 中找到。由于问题只问长度，所以，我认为这个问题也可以在 O(n log n) 中解决。但是我该怎么做呢？
有一个 O(N^2) 动态规划解决方案如下：
令 f(i, j) 是一个 "correct" 子序列以第一个 i 元素之一结束并且恰好由 j 个元素组成的最小总和可以有。
基本情况是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 个元素添加到子序列的末尾）。
这个解决方案的正确性是不言而喻的。
一个很酷的事实：让 A 成为 k 元素的 "correct" 子序列。比A的最后一个元素不小于max(1, 2^(k-2))（证明：k = 1和k = 2都是这种情况。现在我们可以使用归纳法和[=24的事实=])
因此，j在上述动态规划解中的范围大于0..log MAX_A + C，所以在O(N * log MAX_A).
[=56中有效=]
O(N * log MAX_A) 不是 O(N log N)，但是这个解决方案可以很好地用于实际目的。
实际上您根本不需要 DP 解决方案。
先把数字按非降序排列。并从左到右循环。跟踪当前总和。
如果下一个数字不小于总和，则将其添加到 LIS。否则继续下一个数字。
可以证明贪心解是最优解。自己证明吧 ;)
Suppose an array = {2,5,7,8,10}. You need to find the length of Longest Increasing Sub-sequence such that a element is not less than the sum of all elements before it.
在这种情况下，答案可以是 {2,5,7}、{2,5,8} 或 {2,8,10}。所以长度 = 3
这在 O(n^2) 中很容易解决。由于 LIS 长度可以在 O(n log n) 中找到。由于问题只问长度，所以，我认为这个问题也可以在 O(n log n) 中解决。但是我该怎么做呢？
有一个
O(N^2)动态规划解决方案如下：令
f(i, j)是一个 "correct" 子序列以第一个i元素之一结束并且恰好由j个元素组成的最小总和可以有。基本情况是
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个元素添加到子序列的末尾）。
这个解决方案的正确性是不言而喻的。
一个很酷的事实：让
A成为k元素的 "correct" 子序列。比A的最后一个元素不小于max(1, 2^(k-2))（证明：k = 1和k = 2都是这种情况。现在我们可以使用归纳法和[=24的事实=])因此，
[=56中有效=]j在上述动态规划解中的范围大于0..log MAX_A + C，所以在O(N * log MAX_A).
O(N * log MAX_A) 不是 O(N log N)，但是这个解决方案可以很好地用于实际目的。
实际上您根本不需要 DP 解决方案。
先把数字按非降序排列。并从左到右循环。跟踪当前总和。
如果下一个数字不小于总和，则将其添加到 LIS。否则继续下一个数字。
可以证明贪心解是最优解。自己证明吧 ;)