求最接近零的子数组

求最接近0的子数组
问题：给定数组a[n]，求其子数组的最大和。例如输入数组为：

1，-2，3，10，-4，7，2，-5

和最大的子数组为3，10，-4，7，2，因此输出为18.


求数组中最大的子数组的和可以有复杂度为O(n)的扫描算法，
其扩展问题有：
1、求最接近0的子数组
2、求最接近实数t的子数组。

第一个问题比较流行的做法是数组累加和，排序，然后找最接近的两个数，
由于要排序，复杂度挺高的。
有没有像求最大和那样的算法，能在O(N)内求出最接近0的啊？

第二个问题有没有好的解法？

------解决方案--------------------
有一种方法
1）最小个正和
2）最大负数和
3）比较二者的绝对值，取最小的。
不知可不可以达到O(n)


------解决方案--------------------

引用:

Quote: 引用:

这问题我遇到过，用贪心算法。

能说下怎么贪不？
或者直接上code？

我遇到的问题就求最大或者最小的子数组，然后要求是在O（n）内实现。
贪心算法还是比较有名的，网上自己找资料吧。
这是学生时代接触的东西了，现在早就忘了当时怎么做的，只记得是用贪心算法实现的。
只能帮到你这里了。
------解决方案--------------------

引用:

Quote: 引用:

Quote: 引用:

Quote: 引用:

这问题我遇到过，用贪心算法。

能说下怎么贪不？
或者直接上code？

我遇到的问题就求最大或者最小的子数组，然后要求是在O（n）内实现。
贪心算法还是比较有名的，网上自己找资料吧。
这是学生时代接触的东西了，现在早就忘了当时怎么做的，只记得是用贪心算法实现的。
只能帮到你这里了。

最大或者最小子数组是很简单的，知道；
也许最接近0的就没有O(n)的算法吧，
还是谢谢你~

目前是没有。有的话就P=NP了。
------解决方案--------------------

引用:

Quote: 引用:

目前是没有。有的话就P=NP了。

这个的复杂度哪有那么高
n个索引中取2个作为起止，算和 （复杂度(o(n))）
总o(n^2)种，
穷举最多也就o(n^3)复杂度

哦子数组。我看成子集了。

那就对于sum(a[i])做最接近的数。最接近的数这个问题本身有理论下界nlogn，所以排序已经算是不错的办法了。

顺便理论下界的证明是，只考虑t=0的情况，就退化到了判断数组是否有相同元素，这个问题用代数决策树可以做出nlogn的下界的。