AOJ - Problem 0022 : Maximum Sum Sequence

• 問題文

連続した項の和の最大値を出力する問題です。下のソースコードは計算量がO(n^2)です。
ちょっと危ないかと思いきやn<=5000なので大丈夫でした。
またこの問題は最低１つは選択しないといけないようなので、-1,-2,-3という数列なら-1と出力
しなければならないようです。

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	int n, max1, max2, a[5001];

	while( cin >> n , n ){
		for(int i=0 ; i<n ; i++){
			cin >> a[i] ;
		}
		max1 = a[0];

		for(int i=0 ; i<n ; i++){
			int sum = 0;
			for(int j=i ; j<n ; j++){
				sum += a[j];
				max1 = max( max1 , sum );
			}
		}
		cout << max1 << endl;
	}
}