求元素和/个数最大的子数组
O(n^2)算法简单。有没有人对此有更好的算法？
共有1个答案
可以使用二进制搜索。
对于搜索的值x，请考虑数组b[i]=a[i]-x。现在查找长度至少k的最大和子数组。
这是因为长度k的子数组的平均值为(a[p]+...+a[p+k-1])/k。所以我们有：
(a[p] + ... + a[p + k - 1]) / k >= avg
a[p] + ... + a[p + k - 1] >= avg * k
(a[p] - avg) + ... + (a[p + k - 1] - avg) >= 0
-
本节通过求数组的最大和最小值来提高初学者对数组的一些基本应用。 程序运行结果如下： 最高成绩：100 最低成绩：67 将变量 min 与 max 初值设成数组的第 1 个元素后，再逐一与数组中的各元素相比。比 min 小，就将该元索的值指定给 min 存放，使 min 的内容保持最小。同样，当该元素比 max 大时，就将该元素的值指定给 max 存放，使 max 的内容保持最大。for 循环执行完
-
有没有一种方法可以在小于O(n^2)的时间内做到这一点。 O（nlogn）还是O(n)？
-
对于使用分治方法的最大和子数组算法，我需要返回和和子数组。 我能在所有的测试中正确地计算和。然而，我无法计算出正确的子数组。 我的总数（正确）：34 阵列：2 9 8 6 5-11 9-11 7 5-1-8-3 7-2 正确子数组：2 9 8 6 5 我的总数（正确）：50 阵列：31-41 59 26-53 58 97-93-23 84 正确子数组：59 26-53 58 97 我的总数（正确）
-
子数组包含正数和负数。你必须找到一个最大和子数组，使子数组的长度大于或等于k。 下面是我用C++编写的使用Kadane算法的代码。 我的代码工作得很好，但很慢，我想不出任何方法来改进我的代码。我也读过这个问题，找到最长的子数组，它的和可以被K整除，但这不是我想要的，长度也可以大于K。
-
我有一个数组，类似于[1,3,5]。对于这些元素中的每一个，我都需要找到当前元素最高的最长子数组。答案是所有子数组的长度之和。 最终答案=1+2+3=6[单个子数组的长度] 对于这个问题，我可以给出一个强力O(N^2)。有没有更好的办法来解决这个问题？