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

Question

我有一个程序来确定数组中最大的连续总和，但希望将其扩展为使用圆形数组。有没有比将单个数组加倍并调用我的函数来查找 2n 长度数组中所有 n 长度数组的最大总和更简单的方法？

Answer 1

请参阅以下链接：

它使用 Kadane 算法解决了问题。

Answer 2

我认为@spinning_plate 的解决方案是错误的。请您针对给定的情况进行测试。

int arr[] = {-3, 6, 2, 1, 7, -8, 13, 0};

你的方法返回21。

实际的解决方案可以从第6个索引（即13值）开始..到第4个索引（即7值）结束。由于数组是循环的，我们可以从第 6 个索引到第 7 个索引以及从第 0 个索引到第 4 个索引获取连续序列。

上述案例的实际答案是：26

Answer 3

好吧，您实际上不必将数组加倍。您可以通过对现有数组进行索引模 n 来模拟它，或者仅对其进行迭代两次。根据数组的大小和缓存行为，这最多应该比非循环数组的算法慢两倍。

Answer 4

对于给定的问题，
我们将应用kadane算法，我们还将找到具有最大负值的子集。如果删除最大负值，则将以循环顺序给出剩余数组的总和。如果该总和大于最大总和，则最大总和将按循环顺序求和。
该算法的复杂度为 O(n)。

Eg:- arr[i]={10,-3,-4,7,6,5,-4,-1}
      Ans:  max_sum=7+6+5+(-4)+(-1)+10
            Removed_set={-3,-4}
int find_maxsum(int arr[],int n)
{
 int i=0;
 int total=0;
 int maxa=0;
 int mini=0;
 int min_sum=0;
 int max_sum=0;


 while(i<n) 
  {
    maxa=maxa+arr[i];
    total=total+arr[i];
    mini=mini+arr[i];

   if(maxa>max_sum)
     max_sum=maxa; 
   if(mini<min_sum)
     min_sum=mini;
   if(maxa<0)
     maxa=0;
   if(mini>=0)
    mini=0;
}
if(total-min_sum>max_sum)
   max_sum=total-min_sum;
 return max_sum;

}

Answer 5

我假设您使用的是 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;

Answer 6

基于 nikhil 的想法的正确代码：最小总和的元素子数组不能出现在最终的包装或不包装最大和子数组中。

public int maxSum(int[] arr) {
    if (arr.length == 0) return 0;

    int sum = 0;
    int min = Integer.MAX_VALUE;
    int eix = 0;
    for (int i = 0; i < arr.length; i++) {
        sum = sum + arr[i] < arr[i] ? sum + arr[i] : arr[i];
        if (sum < min) {
            min = sum;
            eix = i;
        }
    }
    int max = 0;
    sum = 0;
    for (int i = eix; i < arr.length + eix; i++) {
        int ix = i < arr.length ? i : i - arr.length;
        sum = sum + arr[ix] > arr[ix] ? sum + arr[ix] : arr[ix];
        max = max > sum ? max : sum;
    }

    return max;
}

Answer 7

即使所有数字均为负数，例如 {-1, -2, -3}，此代码也会返回正确答案。
将返回-1；

 public static int maxSubarraySumCircular(int[] A) {

    int maxSum = Arrays.stream(A).max().getAsInt();
    if (maxSum < 0)
        return maxSum;

    int maxKadane = KadaneAlgorithm(A);
    int maxWrap = 0;
    for (int i = 0; i < A.length; i++) {
        maxWrap += A[i];
        A[i] = -A[i];
    }
    maxWrap = maxWrap + KadaneAlgorithm(A);

    return maxWrap > maxKadane ? maxWrap : maxKadane;
}

private static int KadaneAlgorithm(int[] A) {
    int maxSoFar = 0;
    int maxEndingHere = 0;
    for (int i = 0; i < A.length ; i++) {

        maxEndingHere = maxEndingHere + A[i];

        if (maxEndingHere < 0 )
            maxEndingHere = 0;

        if(maxSoFar < maxEndingHere)
            maxSoFar = maxEndingHere;
    }

    return maxSoFar;
}