algorithm - 修改 LIST 使得一个元素大于之前所有元素的总和

Question

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) 中解决。但是我该怎么做呢？

Answer 1

其实你根本不需要DP Solution。
先把数字按非降序排列。并从左到右循环。跟踪当前总和。
如果下一个数字不小于总和，则将其添加到 LIS。否则继续下一个数字。
可以证明贪心解是最优解。自己证明 ;)