算法题（127）：最大子段和

审题：
本题需要我们找到n个整数中连续且非空的最大子段和

思路：
方法一：前缀和

我们的思路是将每个索引位置的最大子段和求出，然后用answer进行max维护，最后输出answer即可

最大子段和怎么求？

子段和 = f[i] - f[left-1]，而f[i]是确定的，所以我们只需要找到i之前的最小f[left]即可让子段和最大

i之前的最小f[left]怎么求？

我们可以从i==1开始用min维护

解题：
 

#include<iostream>
using namespace std;
int n;
const int N = 2e5 + 10;
long long f[N];//前缀和
long long answer = -1e20;
int main()
{cin >> n;long long num;for (int i = 1; i <= n; i++){cin >> num;f[i] = f[i - 1] + num;}long long  minnum = 0;//f[i]前面的最小子段和for (int i = 1; i <= n; i++){answer = max(answer, f[i] - minnum);minnum = min(minnum, f[i]);}cout << answer << endl;return 0;
}

第一步：录入数据并计算前缀和

第二步：计算索引为i位置的最大子段和

第三步：输出数据

注意：

1.由于涉及数据的加减，所以最好使用longlong数据类型

2.minnum其实就是当前最小的前缀和

P1115 最大子段和 - 洛谷