O(n)中最大的子数组总和，使用C ++中的前缀总和

问题陈述

给定一个正整数和负整数数组，找出该数组中的最大子数组总和

示例

如果输入数组为− {-12，-5，4，-1，-7，1，8，-3}，则输出为9

算法

• 计算输入数组的前缀和。

• 初始化-min_prefix_sum = 0，res =-无穷大

• 保持i = 0到n的循环。（n是输入数组的大小）。

• cand = prefix_sum [i] –迷你

• 如果cand大于res（到目前为止最大子数组和），则按cand更新res。

• 如果prefix_sum [i]小于min_prefix_sum（到目前为止的最小前缀和），则用prefix_sum [i]更新min_prefix_sum。

• 返回资源

示例

#include <bits/stdc++.h>
using namespace std;
int maximumSumSubarray(int *arr, int n){
   int minPrefixSum = 0;
   int res = numeric_limits<int>::min();
   int prefixSum[n];
   prefixSum[0] = arr[0];
   for (int i = 1; i < n; i++) {
      prefixSum[i] = prefixSum[i - 1] + arr[i];
   }
   for (int i = 0; i < n; i++) {
      res = max(res, prefixSum[i] - minPrefixSum);
      minPrefixSum = min(minPrefixSum, prefixSum[i]);
   }
   return res;
}
int main(){
   int arr[] = {-12, -5, 4, -1, -7, 1, 8, -3};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Result = " << maximumSumSubarray(arr, n) <<endl;
   return 0;
}

输出结果

当您编译并执行上述程序时。它产生以下输出-

Result = 9