aoj0022:Maximum Sum Sequence

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0022&lang=jp

解法

全区間を試す。愚直に3重ループとかしちゃうとO(N^3)となり死ぬ。区間の始点だけ決めて終点をだんだん遠くしていきながら最大値を求めるとよい。そうすると一つ前の結果を再利用できるので3つめのfor文が必要なくなり、O(N^2)となる。

コード

#include<bits/stdc++.h>
using namespace std;
int a[5000],n;
signed main(){
    while(cin>>n,n){
        for(int i=0;i<n;i++)cin>>a[i];
        int ma=LLONG_MIN;
        for(int i=0;i<n;i++){
            int cur=0;
            for(int j=i;j<n;j++){
                cur+=a[j];
                ma=max(ma,cur);
            }
        }
        cout<<ma<<endl;
    }

    return 0;
}