数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会科学
时尚研究
法律研究使用 C++ 中的前缀和以 O(n) 计算最大子数组和
问题陈述
给定一个正整数和负整数数组，找出该数组中的最大子数组和
示例
如果输入数组为 {-12, -5, 4, -1, -7, 1, 8, -3}，则输出为 9
算法
计算输入数组的前缀和。
初始化 - min_prefix_sum = 0，res = - 无穷大
维护从 i = 0 到 n 的循环。（n 是输入数组的大小）。
cand = prefix_sum[i] - mini
如果 cand 大于 res（目前为止的最大子数组和），则按 cand 更新 res。
如果 prefix_sum[i] 小于 min_prefix_sum（目前为止的最小前缀和），则按 prefix_sum[i] 更新 min_prefix_sum。
返回 res
示例
#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
更新于: 2020 年 1 月 30 日
635 次浏览
广告