求解最大子段和問題----分治 蠻力 dp

【問題描述】給定一個有n（n≥1）個整數的序列，要求求出其中最大連續子序列的和。

例如：

序列（-2，11，-4，13，-5，-2）的最大子序列和為20

序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）

的最大子序列和為16。

規定一個序列最大子段和至少是0，如果小于0，其結果為0。

蠻力法

窮舉所有連續子序列來得到。

設含有n個整數的序列a[0…n-1]，窮舉所有的連續子序列a[i…j]，求出它的所有元素之和thisSum，并通過比較将最大值存放在maxSum中，最後傳回maxSum。

long maxSubSum1(int a[],int n)
{       int i,j,k;
　　long maxSum=a[0],thisSum; 
　　for (i=0;i<n;i++)     //兩重循環窮舉所有的連續子序列
　　{  for (j=i;j<n;j++)
　　　　{   thisSum=0;
　　　　　 for (k=i;k<=j;k++)
　　　　　　　　thisSum+=a[k];
　　　　　 if (thisSum>maxSum)  //通過比較求最大連續子序列之和
　　　　　　　　maxSum=thisSum;
　　　　}
　　}
　　return maxSum;
}
           

改進的蠻力法

long maxSubSum2(int a[],int n)
{      int i,j;
　　long maxSum=a[0],thisSum;
　　for (i=0;i<n;i++)                 // i是子列左端位置
　　{     thisSum=0;                // thisSum是從a[i]到a[j]的子列和
　　　　for (j=i;j<n;j++)          // j是子列右端位置
　　　　{      thisSum+=a[j];
　　　　　　 if (thisSum>maxSum)
　　　　　　　　maxSum=thisSum;
　　　　}
　　}
　　return maxSum;
}
           

分治法

long maxSubSum3(int a[]，int left，int right) 
//求a[left..right]序列中最大子段和
{  int i，j;
   long maxLeftSum，maxRightSum;
   long maxLeftBorderSum，leftBorderSum;
   long maxRightBorderSum，rightBorderSum;
   if (left==right)  //子序列隻有一個元素時
   {　　if (a[left]>0)  //該元素大于0時傳回它
　　　　　　return a[left];
　　　　else   //該元素小于或等于0時傳回0
　　　　　　　return 0; 
   } 
　　int mid=(left+right)/2;   //求中間位置
　　maxLeftSum=maxSubSum3(a，left，mid); //求左邊
　　maxRightSum=maxSubSum3(a，mid+1，right); //求右邊
　　maxLeftBorderSum=0，leftBorderSum=0;
　　for (i=mid;i>=left;i--)　   //求出以左邊加上a[mid]元素
　　{  leftBorderSum+=a[i];　   //構成的序列的最大和
　       if (leftBorderSum>maxLeftBorderSum)
　　　　　　maxLeftBorderSum=leftBorderSum;
　　}
　　maxRightBorderSum=0，rightBorderSum=0;
　　for (j=mid+1;j<=right;j++)  //求出a[mid]右邊元素
　　{  rightBorderSum+=a[j];    //構成的序列的最大和
　　   if (rightBorderSum>maxRightBorderSum)
　　　　　　maxRightBorderSum=rightBorderSum;
　　}
　　return max3(maxLeftSum，maxRightSum，
     maxLeftBorderSum+maxRightBorderSum); 
} 
           

最優算法(就周遊一次)

從頭開始掃描數組a，用sum（初值為0）記錄目前子序列之和，用max（初值為0）記錄最大連續子序列和。

如果掃描中遇到負數，目前子序列和sum将會減小，若sum為負數，表明前面已經掃描的那個子序列可以抛棄了，則放棄這個子序列，重新開始下一個子序列的分析，并置sum為0。

若這個子序列和sum不斷增加，那麼最大子序列和max也不斷增加。

int maxSubSum4(int a[],int n)
{　 int i,max=0,sum=0;
　　for (i=0;i<n;i++)
　　{  sum+=a[i];//向右累加
　　　　if (sum<0) //若目前子序列和為負數，重新開始下一子序列
　　　　　　sum=0;
　　　　if (sum>max)//發現更大和則更新目前結果
　　　　　　max=sum;
　　}
　　return max;
}
           

類似動态規劃