最大子数组和

最大子数组和

(100/100 分数)

题目描述

给定一个数组a[0,...,n-1],求其最大子数组(长度>=1)和

输入描述

第一行一个整数n(1<=n<=5000)，然后依次输入n个整数（每个整数范围[-5000, 5000]）

输出描述

输出一个整数表示最大子数组和

样例输入

5
1 -1 1 1 -1

样例输出

2

/*students please write your program here*/
#include <iostream>

using namespace std;

int main() {
	int n;
	cin >> n;

	int sum = 0;
	int currentSum = 0;
	int temp;
	for (int i = 1; i <= n; i++) {
		cin >> temp;
		currentSum += temp;

		if (currentSum > sum)
			sum = currentSum;
		if (currentSum < 0)
			currentSum = 0;
	}
	cout << sum << endl;
}