用于从包含最大求和的整数数组中提取子数组的算法

Algorithm for extracting a subarray out of an integer array, which contains the maximum summation

本文关键字：数组 提取 算法 整数 包含最 求和 和的 用于      更新时间：2023-09-26

有一个整数数组（正整数和负数）。请建议一种算法，该算法将为您提供最大总和的子数组。例：

int a[] = new int[]{2,3,-1,4,5,7,8,13,-20};

那么答案应该是{4,5,7,8,13}为4 + 5 + 7 + 8 + 13 = 37.

我无法为此问题设计算法。

以下是此问题的线性解决方案： 

long getMaximumSubarraySum(int[] a) {
    int start = 0; 
    int end = 0;
    long result = 0; // I assume that an empty subarray is allowed.
    long minPrefixSum = 0;
    int minPrefixSumPos = -1;
    long currentPrefixSum = 0;
    for (int i = 0; i < a.length; i++) {
        currentPrefixSum += a[i];
        if (currentPrefixSum - minPrefixSum > result) {
             result = currentPrefixSum - minPrefixSum;
             start = minPrefixSumPos + 1;
             end = i + 1;
        }
        if (currentPrefixSum < minPrefixSum) {
             minPrefixSum = currentPrefixSum;
             minPrefixSumPos = i;
        }
    }
    // The resulting subarray is [start; end).
    return result;
}

这个算法背后的想法非常简单：让我们看一下前缀总和。那么答案是 max(prefixSum[i] - prefixSum[j]) 的最大值，其中 j < i 对于所有i。这正是此代码的作用：它遍历输入数组，维护当前前缀总和和最小前缀总和，并选择最佳答案。

几个月前我已经解决了这个问题，所以我将为您提供算法。由您编写程序。

该程序的要点是，当您在数组中遇到否定数字时，总和会减少。因此，当这种情况发生时，您将数组分为 3 个部分。
1） 总和到现在
2） 到目前为止的总和 + 否定值（如果有连续否定数，则为值）3） （2）
+ 直到遇到另一个否定数

的总和 给定这 3 个部分，选择具有最大值的部分并将其存储在变量中。此值将成为下一次迭代的 （1）。继续，直到到达阵列的末尾

这是伪代码：

 do until end of array{
        b=compute_b() //Compute sum till you encounter negetive number
        c=compute_c() //Compute sum till you encounter a positive number
        a=max+b+c;
        if(a>c)
        {
             if(a>max)
             {
                      max=a;
             }
         }
         else
         {
              if(c>max)
              {
                    max=c;
              }
          }
    }
    print max

var a = [2,3,-1,4,5,7,8,13,-20];
var positiveNums =  a.filter(function(num){
  return num > 0
}); // [2,3,4,5,7,8,13]
var sum = positiveNums.reduce(function(a, b){
  return a+b;
}); // 42
相关文章：