読者です 読者をやめる 読者になる 読者になる

らての精進日記

修行をします

aoj0022:Maximum Sum Sequence

解法

全区間を試す。愚直に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;
}