[TOC]
## 和最大子序列
### 题目描述
对于一个给定的长度为N的整数序列A，它的“子序列”的定义是：A中非空的一段连续的元素（整数）。你要完成的任务是，在所有可能的子序列中，找到一个子序列，该子序列中所有元素的和是最大的（跟其他所有子序列相比）。程序要求你输出这个最大值。
* * * * *
### 输入
输入文件的第一行包含一个整数N，第二行包含N个整数，表示A。 其中1 <= N <= 100000 -10000 <= A[i] <=10000
* * * * *
### 输出
输出仅包含一个整数，表示你算出的答案。
* * * * *
### 代码实现
```
#include<iostream>
#include<cmath>
using namespace std;
int main(){
int n;
cin >> n;
int arr[n+1];
for(int i = 1; i <= n; i ++){
cin >> arr[i];
}
int sum =0;
int max = -10005;
for(int i = 1; i <= n; i ++){
sum += arr[i];
if(sum > max){
max = sum;
}
if(sum < 0){
sum = 0;
}
}
cout << max << endl;
return 0;
}
```
### 分析
完整代码蒟篛已经在前面呢贴出来了。
* * * * *
核心代码如下
```
for(int i = 1; i <= n; i ++){
sum += arr[i];
if(sum > max){
max = sum;
}
if(sum < 0){
sum = 0;
}
}
```
从数组的第一个元素开始遍历，sum加上当前元素的值，然后判断是否大于当前的最大值，如果大于，则将sum赋值给当前最大值。如果发现sum已经小于0，那么我们就将sum置为0，这是很关键的一步。若是sum<0,那么sum再加上后面你的数值，相当于是在拉后腿，我们应该当断则断，把sum置为0，这样可以得到最优解。
