首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >门限下最大绝对子阵列和的算法

问门限下最大绝对子阵列和的算法
EN

Stack Overflow用户
提问于 2017-08-22 20:33:00
回答 1查看 278关注 0票数 0

我试图通过标题传达的是以下练习:给出一个正负数字列表,其中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)解决方案刚刚遍历了每个可能的子数组和。它没有重新计算每一个和,而只是添加了一个新的数字。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 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)。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/45817779

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档