循环缓冲区中的最大连续和

Question

我有一个程序来确定数组中最大的连续和,但是想要扩展它以使用圆形数组.是否有更简单的方法来做到这一点,而不是加倍单个数组并调用我的函数来找到2n长度数组中所有n长度数组的最大总和？

Answer 1

请参阅以下链接:

它使用Kadane Algorithem解决了一个问题.

http://www.geeksforgeeks.org/maximum-contiguous-circular-sum/

Answer 2

我假设您使用的是 O(n) 算法，该算法继续添加总和，跟踪最大值，仅当总和为负数时才重新启动。要捕获圆形数组的情况，您唯一需要做的就是将相同的原理应用于圆形方面。当您到达原始算法中的数组末尾时，继续循环到开头，直到低于最大值或达到当前范围的开头（但我认为这是不可能的，因为如果解决方案是完整数组，我们应该在第一次通过时就看到了这一点），在这种情况下你就完成了。

max_start=0; max_end =0; maxv = 0; sum 0;
for i in range(arr):
    sum+= arr[i];
    if sum<0:
       sum=0; max_start =i;
    if maxv<sum:
       maxv=sum; max_end = i;

#seocnd pass
for i in range(max_start):
    sum+= arr[i];
    if sum<0:
       break;
    if maxv<sum:
       maxv=sum;max_end = i;