[開拓]杭電1003(最大の子配列問題)

http://acm.hdu.edu.cn/showproblem.php?pid=1003 問題そのものについては、時間制限を考慮しないで、解法は多くのまず暴力的に解決できます.三重循環で解決して、一回の循環を省略します.ここでコードを提供します.

#include <stdio.h>
 int MaxSum(int* A,int n,int* i,int* j) 
 { 
     int maximum=-100000,sum,t,p; 
     for (*i=0;*i<n;(*i)++) 
     {
          sum=0;  
          for (*j=*i;*j<n;(*j)++)
           {
               sum+=A[*j]; 
               if (sum>maximum) 
               {    maximum=sum; t=*i;p=*j;
                }
           }
      }
       *i=t+1; *j=p+1; 
       return maximum; 
   } 
int main() 
{
    int n,i,j,m,a[100001],x,y;
    scanf("%d",&n);
    for (i=0;i<n;i++) 
    { 
        scanf ("%d",&m); 
        for (j=0;j<m;j++) 
            scanf ("%d",&a[j]);
            printf ("Case %d:
%d %d %d

",i+1,MaxSum(a,m,&x,&y),x,y); 
            } 
return 0; 
}

第二の最適化は、継続的にサイクルを省略し、分割戦略を用いて全体の配列を分解することができます.A[low,mid]、A[mid+1,high]の3つのケースに分けて1.maximumはA[low,mid]の2.maximumはA[mid+1,high]の中にあります.中間点low==i=mid=j=この中で最大値を超えて更新します.

int leftsum=ptrA[mid];
//      
int maxleft=mid;
//    
int sum=0; 
for (int i=mid;i>=low;i--) 
{ 
   sum+=ptrA[i]; 
   if (sum>=leftsum) 
   { 
      leftsum=sum; maxleft=i; 
   } 
} 
//          ，             ，      
//  ，   ，              

考え方を変えて、動態計画はどうしてある人が最適化を動態計画としているのか分かりません.

int max(int x,int y) 
{   
   return (x>y?x:y);
} 
int maxsum(int *A,int n) 
{ 
   start[n-1]=A[n-1]; 
   ALL[n-1]=A[n-1]; 
   for (i=n-2;i>=0;i--) 
   { 
      start[i]=max(A[i],A[i]+start[i+1]);
      ALL[i]=max(start[i],ALL[i+1]);               
   } 
return ALL[0]; 
}
//          
#include<iostream> 
#define inf 0x3f3f3f using namespace std;
int a[100001],s[100001],t[100001]; 
int main() 
{ 
   int m,n,i,j,p,q,max; 
   cin>>n; 
   for(i=1;i<=n;i++) 
   { 
      if(i!=1) 
      cout<<endl; 
      cin>>m; 
      for(j=1;j<=m;j++) 
      cin>>a[j];  
      t[0]=-1; 
      s[0]=0; 
      for(j=1;j<=m;j++) 
      { 
         if(t[j-1]>=0) 
         { 
            t[j]=t[j-1]+a[j];
            s[j]=s[j-1];
         } 
         else 
         { 
            t[j]=a[j]; 
            s[j]=j; 
         } 
      } 
      max=-inf;
      p=0;
      q=0; 
      for(j=1;j<=m;j++) 
      if(t[j]>max) 
      { 
         max=t[j]; 
         p=s[j]; 
         q=j; 
      } 
   cout<<"Case "<<i<<":"<<endl; cout<<max<<" "<<p<<" "<<q<<endl;        } 
   return 0; 
} 

ダイナミック企画に初めて触れたので、最初は分かりませんでしたが、他の人の分析を見たらよく分かりました.ここで引用のリンクを提供します.http://alorry.blog.163.com/blog/static/6472570820123801223397/
シーケンスa［n］全体に対しては、そのすべてのサブシーケンスが多いが、それらを分類することができる.最後のサブシーケンスです.この中には必ず含まれます.
a[0]で終わるサブシーケンスはa[0]のみa[1]で終わるサブシーケンスはa[0]a[0]a[1]とa[1]でa[2]で終わるサブシーケンスはa[0]a[0]a[1]a[1]/a[1]a[1]a[2]…a[i]で終わるサブシーケンスはa[0]a[1]a[1]…………[a[a]…[a]……[a]……[a]…………[a[a]…[a]…[a]……[a]…[a]………[a[a[a]…………………[a]……[a]……[i]で終わるサブシーケンスはa[i]…[a[a]…[a[a a[i-1]a[i]/…/a[i-1]a[i]/a[i]
a［0］〜a［n］で終わるすべてのサブシーケンスパケットは、シーケンス全体のサブシーケンスを構成している.
このようにして、私たちはa［0］〜a［n］で終わるこれらのパケットのサブシーケンスの中の各グループの最大サブシーケンスとだけが必要です.そして、n個のパケットの最大サブシーケンスおよび中から、シーケンス全体の最大サブシーケンスの和を選択する.
観察により、0,1,2,…,nで終わるパケットの中で、maxsum a[0]=a[0]maxsum a[1]maxsum a[1]=max(a[0]+a[1]==max(maxsum a[0]+a[1],a[1])maxsum a[2]=max[2]=max[1]=max[a[1]=max[1]=max[a[1]=max[1]=max[1]=max[1]=max[/a[a[1]=max[a[1]、[a[1]=max]=max=max[1]、[a[1]=max[1]、[a[1]]ma+ a[2],a[2]=max(maxsum a[1]+a[2],a[2])...これに類推します.共通の式が出ます.maxsum a[i]=max(maxsum a[i-1]+a[i],a[i]