更新时间:2022-05-24 22:18:26
假设你知道答案是 x,这意味着最大子集的总和等于 x.你可以通过贪心算法O(n)来验证这个假设.(从左到右遍历数组并选择项目,直到该子集的总和小于 x).现在您可以对 x 进行二分搜索,并找到 x 的最小值.这个算法的复杂度是O(nlogn).
Assume you know the answer is x which means sum of the maximum subset is equal to x. You can verify this assumption by a greedy algorithm O(n). (Traverse the array from left to right and pick items until the sum of that subset is lower than x). Now you can binary search on x and find the minimum value for x. The complexity of this algorithm is O(nlogn).