我试图通过标题传达的是以下练习:给出一个正负数字列表,其中0
例如:列表:1 -4 5 6 -3 -2 14
如果阈值是4,则最佳解决方案是{-4}
如果阈值是9,则最佳解决方案是{-3 -2 14}
如果阈值是100,则最佳解决方案是{5 6 -3 -2 14}
如果阈值是7,那么最好的解决方案是{-4 5 6}
如果阈值为2,则最佳解决方案为{-2}
对于那些对我是如何处理这个问题感兴趣的人:
我使用的O(n^2)解决方案刚刚遍历了每个可能的子数组和。它没有重新计算每一个和,而只是添加了一个新的数字。
发布于 2017-08-22 23:18:00
计算部分和:P(i) = sum(a[0]...a[i])
对于给定的位置对x,y (x <= y),和是P(y) - P(x-1)。因此,如果我们固定y,那么你在寻找大于或等于y- target的最小值。
因此,迭代集合并将项目插入平衡树中(就像大多数语言中的集合一样)。然后,您可以在集合中查找该值并返回值(在C++中,有一个upper_bound,它几乎就是您所需要的)。继续这样做,找到满足条件的最大组合。
查找和插入应该是O( logN),所以总体上解决方案将是O(N LogN)。
https://stackoverflow.com/questions/45817779
复制相似问题