NYOJ 44子串和

住所:http://acm.nyist.net/JudgeOnline/problem.php?pid=44
考え方:
この問題もダイナミックプランニングの問題で、最初はミサイル迎撃の妨害を受けて、データの一番後ろから処理しなければならないと思っていましたが、結局自分は考えが間違っていて、違和感を感じて、それから書いた後はやはり間違っていました.それから最初から処理して、WAは3回もして、多くの小さい細部ができていないことを発見しました.最後のコミット、AC.問題を解く構想は、前から後へデータを処理し、前のデータが0より大きいかどうかを判断し、絶えず累積し、最後に最大の和を出力することである.いくつかの小さな細部と思想はコードと注釈に現れることができます.

 1 #include<stdio.h>

 2 int a[1000001];//          ，    

 3 int main()

 4 {

 5     int i,n,sum,num;

 6     scanf("%d",&n);

 7     while(n--)

 8     {

 9         sum=-100;

10         scanf("%d",&num);

11         for(i=1;i<=num;i++)//   “=“ ，    。

12         {  

13            scanf("%d",&a[i]);

14            if(a[i-1]>0)

15            a[i]+=a[i-1];//    ，          0  ，      。

16            if(a[i]>sum) sum=a[i];//        。

17         }

18         printf("%d
",sum);

19     }

20         return 0;

21 }

 
 
nyoj 44文字列和は古典的な動的計画問題であり,104題は44題の一次元最大と行列に拡張し,サブ行列の最大和を求める.
考え方はほぼ一致していますが、まずnyoj 44についてお話ししましょう.最大フィールドと問題は列挙,分治,動的計画で解決でき,時間的複雑度はそれぞれO(n^2),O(nlogn),O(n)であった.
dpの状態方程式:b[j]=max{b[j-1]+a[j],a[j]},1<=j<=n;if b[j-1] >0, b[j] = b[j-1]+a[j];else b[j] = a[j];

 1 int maxsum(int n, int *a)

 2 {

 3     int i;

 4     int sum = 0, b = 0;

 5     for(i = 0; i < n; i++)

 6     {

 7         if(b > 0)

 8             b += a[i];

 9         else b = a[i];

10         if(b > sum)

11             sum = b;

12     }

13     return sum;

14 }