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