sum - x 个元素的最大连续子序列和

Question

所以我想出了一个我已经查看和搜索但没有找到答案的问题......获得x元素的最大连续子序列和的最好（并且说最好，我的意思是最快）方法是什么？

想象一下我有：A[] = {2, 4, 1, 10, 40, 50, 22, 1, 24, 12, 40, 11, ...}。然后我问：

"What is the maximum contigous subsequence on array A with 3 elements?"

请想象一下这个数组有超过 100000 个元素......有人可以帮我吗？

谢谢你的时间，你的帮助！

Answer 1

我用谷歌搜索了一下，发现了这个：

使用分而治之的方法，我们可以在 O(nLogn) 时间内找到最大子数组和。以下是分治算法。

这个问题的 Kadane 算法需要 O(n) 时间。因此，Kadane 的算法优于分治法

见代码：

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far