会津オンラインジャッジ：Maximum Sum Sequece

[みけCAT]

問題は
http://rose.u-aizu.ac.jp/onlinejudge/Pr ... 22&lang=jp
です。
この問題に対し、以下のソースコードを書きました。

コード:

#include <stdio.h>

int main(void) {
	long long a[5000];
	long long ask[5000];
	int max;
	int i;
	int j;
	int k;
	int sign;
	long long saidaiti;
	long long now;
	while(1) {
		scanf("%d",&max);
		if(max==0)break;
		for(i=0;i<max;i++)scanf("%lld",&a[i]);
		for(i=0,j=-1,sign=0;i<max;i++) {
			if(a[i]*sign<=0 && a[i]!=0) {
				sign=(a[i]>0)?1:-1;
				j++;
				ask[j]=0;
			}
			ask[j]+=a[i];
		}
		for(i=0;i<=j;i++) {
			if(ask[i]>=0)break;
		}
		if(i>j) {
			saidaiti=a[0];
			for(i=1;i<max;i++) {
				if(a[i]>saidaiti)saidaiti=a[i];
			}
		} else {
			max=j+1;
			saidaiti=ask[0];
			for(i=1;i<=max;i++) {
				for(j=0;j<=max-i;j++) {
					now=0;
					for(k=j;k<j+i;k++)now+=ask[k];
					if(now>saidaiti)saidaiti=now;
				}
			}
		}
		printf("%d\n",saidaiti);
	}
	return 0;
}

Acceptedとはなったのですが、時間が00:50secもかかっています。
連続する符号が同じ数か0をまとめてから総当たりで調べるコードになっています。
やはり総当たりの部分が遅いのだと思いますが、どうしたら速くなるでしょうか？
よろしくお願いします。

[box]

それだけの時間がかかった理由がアルゴリズムに問題があるためなのか、
それともPCのスペックが低いためなのか、質問文からは判断できません。

これで、他にどういう情報を提示すればいいか、わかりましたね？

「どうしたら速くなるか」という問いに対する一つの答えは、
「スーパーコンピューターで実行する」です。

[五反田]

そのアルゴリズムだと入力の個数nに対してO(n^3)で(3重のforループがあるため最大でn^3に比例する時間がかかってしまいます)、ちょっと遅いので、アルゴリズムを変更するべきでしょう。

たとえば、入力に対して、それまでの入力の和を全て保持する配列Sを用意して、S_n=a_1+・・・+a_nとすれば、a_i～a_j(i<=j)までの和は
S_j-S_(i-1)で求められます。
その最大値を計算して出力するようにすれば、結構早くなるはずですよ。
(これは2重のforループでできるので、O(n^2)のオーダーになりますね。)

また、もっと早くしたければ、(AOJでは上のアルゴリズムで十分でしょうけれど)、O(n)のアルゴリズムも知られています。
よければ調べてみてください。

[みけCAT]

「どうしたら速くなるか」という問いに対する一つの答えは、
「スーパーコンピューターで実行する」です。

最終的な実行環境は会津オンラインジャッジのサーバーに限られているので、
それでは意味がないと思います。

たとえば、入力に対して、それまでの入力の和を全て保持する配列Sを用意して、S_n=a_1+・・・+a_nとすれば、a_i～a_j(i<=j)までの和は
S_j-S_(i-1)で求められます。

この方法で無事00:00secでAcceptされました。
思えば第９回日本情報オリンピック本選の問題１と同じ原理ですね。
（私は恥ずかしながらこの問題もできませんでした）
ありがとうございました。
とりあえず解決にさせていただきます。

コード:

#include <stdio.h>

int main(void) {
	long long a[5000];
	long long ask[5001];
	int max;
	int i;
	int j;
	int sign;
	long long saidaiti;
	long long now;
	while(1) {
		scanf("%d",&max);
		if(max==0)break;
		ask[0]=0;
		for(i=0;i<max;i++)scanf("%lld",&a[i]);
		for(i=0,j=0,sign=0;i<max;i++) {
			if(a[i]*sign<=0 && a[i]!=0) {
				sign=(a[i]>0)?1:-1;
				j++;
				ask[j]=0;
			}
			ask[j]+=a[i];
		}
		for(i=1;i<=j;i++) {
			if(ask[i]>=0)break;
		}
		if(i>j) {
			saidaiti=a[0];
			for(i=1;i<max;i++) {
				if(a[i]>saidaiti)saidaiti=a[i];
			}
		} else {
			max=j+1;
			saidaiti=ask[1];
			for(i=1;i<max;i++)ask[i]+=ask[i-1];
			for(i=1;i<=max;i++) {
				for(j=0;j<=max-i;j++) {
					now=ask[j+i]-ask[j];
					if(now>saidaiti)saidaiti=now;
				}
			}
		}
		printf("%lld\n",saidaiti);
	}
	return 0;
}