無題

[pon]

与えられた数列の内いくつかの数が連続した和の最大値を求めるprogramを書け。という問題です。

http://rose.u-aizu.ac.jp/onlinejudge/Pr ... 22&lang=jp

#include<cstdio>
using namespace std;
int main(){
while(1){
long long int n;
scanf("%lld",&n);
if(n == 0){
break;
}
long long int wa[10001]={0};
for(long long int loop=1;loop<=n;loop++){
long long int aa;
scanf("%lld",&aa);
wa[loop] = wa[loop-1] + aa;
}
long long int max=-3333333;
int flag=0;
for(long long int loop=1;loop<=n;loop++){
for(long long int fir=1;fir<=n-loop+1;fir++){
long long int ret=wa[fir+loop-1]-wa[fir-1];
if(ret > max || flag==0){
max=ret;
flag=1;
}
}
}
if(max!=0){
printf("%lld\n",max);
}
}
}

このようなprogramを組んだのですが、Wrong Answerとなってしまいます。何がダメなのでしょうか。Wrong Answerとなる理由が分からず、全てlong longにしてみたのですが…

[mats]

プログラムを読み解けていませんが、

n:2
a1:-5、a2:0

の時は何が出力されますか？
パッと見では、少なくとも0は出力されないように見えますが…

[初級者]

自分には、「連続した項の和の最大値」の意味と、
入力例と出力例との関係がさっぱりわかりません。

どなたか解説していただけないでしょうか？

[フリオ]

　
>入力例と出力例との関係
　
　例の3つの数列
1)-5 -1 6 4 9 -6 -7
2)1 2 3 2 -2 -1 1 2 3 2 1 -2 1
3)1000 -200 201
に対して、
1)の場合は、3~5項の和、6 + 4 + 9 == 19
2)の場合は、1~11項の和、1 + 2 + 3 + 2 + -2 + -1 + 1 + 2 + 3 + 2 + 1 == 14
3)の場合は、1~3項の和、1000 + -200 + 201 ==　1001
が、"連続する項の和の最大値"になります。

ponさんへ、
"連続する項"とは、1項でもいいのでしょうか、それとも、2項以上でしょうか。

[初級者]

あぁ、項の数が先頭にあるのを完全に見落としてました。

[初級者]

考え方はこういうことかな？

第１項～第ｎ項の和
第２項～第ｎ項の和
第３項～第ｎ項の和
…
第ｎ項～第ｎ項の和

のｎ個の数値の最大を求める。

[mats]

> 初級者さん

その書き方なら、

第1項～第1項の和、第1項～第2項の和、第1項～第3項の和、…、第1項～第n項の和
第2項～第2項の和、第2項～第3項の和、…、第2項～第n項の和
…
第(n-1)項～第(n-1)項の和、第(n-1)項～第n項の和
第n項～第n項の和

なので、n(n+1)/2個の数字の最大かと思われます


> ponさん

if(max!=0){
を
if(flag!=0){
に直せばAcceptedになると思います

老婆心ですが、今後コンテストに参加する予定なら、
O(n^2)でなくO(n)のアルゴリズムを使った方がいいです

[初級者]

私の考え方には誤りがありました。

[pon]

debugの時に0が大量に出てきた時に消すのを忘れていただけでした。どうすればO(n)になりますか?
素直に組むと最初O(n^3)になってTLEしたので、O(n^2)に組みなおしたのですが…

[mats]

#include<iostream>
using namespace std;
int main(){
int n, i, ans, temp, a[5001];
while(cin>>n,n){
for(i=0;i<n;i++)scanf("%d",&a);
ans=-999999,temp=0;
for(i=0;i<n;i++){
temp = max(temp+a, a);
ans = max(ans, temp);
}
cout<<ans<<endl;
}
return 0;
}

このプログラムだとO(n)で解けます

[pon]

>matsさん
確かにそうですね。勉強になりました。ありがとうございました。