前缀和———最大子数组和

点击查看代码

//前缀和 ——> 快速求出数组中，某一段的区间和
//第一步：先预处理出来一个前缀和数组
//f[i] 表示：区间[1, i]中所有元素的和，f[i] = f[i - 1] + a[i]
//第二步：利用前缀和数组//注意事项：使用前缀和数组时， 下标必须从1开始计数（可以避免越界问题）//求数组中的最大子数组和#include <iostream>
// 引入头文件，用于LLONG_MIN（long long类型的最小值）
#include <climits>  using namespace std;const int N = 1e4 + 10;
long long f[N];  // 前缀和数组，f[i]表示前i个元素的和int main(){int n;cin >> n;int x;// 第一步：计算前缀和数组for(int i = 1; i <= n; i++){cin >> x;f[i] = f[i - 1] + x;}// 第二步：利用前缀和求最大子数组和long long ret = LLONG_MIN;  // 初始化为long long的最小值，避免溢出long long prevmin = f[0];   // 初始化为前缀和的第0项（即0）for(int i = 1; i <= n; i++){// 当前i位置的最大子数组和 = 前缀和f[i] - 之前最小的前缀和ret = max(ret, f[i] - prevmin);// 更新之前的最小前缀和（包含当前f[i]）prevmin = min(prevmin, f[i]);}cout << ret << endl;return 0;
}