對“最大子序列和問題”的一點思考
窮舉法是最容易想出的解法，反正就是把所有能舉出的子序列都算一遍和，找出最大的一個就是，復雜度O(N*N)。
int MaxSubSeqSum(int a[],int left,int right)
{
if(left==right)
{
return a[left];
}
int mid = (left+right)/2;
int i,lSum=0,rSum=0,tmpLMax=0,tmpRMax=0;
for(i=mid;i>=left;--i)
{
lSum+=a[i];
if(lSum>tmpLMax)
{
tmpLMax = lSum;
}
}
for(i=mid+1;i<=right;++i)
{
rSum+=a[i];
if(rSum>tmpRMax)
{
tmpRMax = rSum;
}
}
int overMax = tmpLMax+tmpRMax;
int lMax = MaxSubSeqSum(a,left,mid);
int rMax = MaxSubSeqSum(a,mid+1,right);
return max(max(overMax,lMax),rMax);
}
int MaxSubSeqSum2(int a[],int len)
{
int tmpSum=0,maxSum = 0;
for(int i=0;i<len;++i)
{
tmpSum+=a[i];
if(tmpSum>maxSum)
{
maxSum = tmpSum;
}
else if(tmpSum<0)
{
tmpSum=0;
}
}
return maxSum;
}
對于分治法來說，“分“是比較簡單的，對半分成求解左右兩個序列的最大子序列，不過終止條件應該是什么呢？我的想法是到只剩一個元素的序列的話，直接返回這個元素就是了，可書上都是如果大于0，返回此元素，若小于0，則返回0，這里想不明白。最難的部分應該是“治”，要考慮跨左右兩個子序列的情況。
int MaxSubSeqSum(int a[],int left,int right){
if(left==right) {
return a[left]; } int mid = (left+right)/2; int i,lSum=0,rSum=0,tmpLMax=0,tmpRMax=0; for(i=mid;i>=left;--i) { lSum+=a[i]; if(lSum>tmpLMax) { tmpLMax = lSum; } } for(i=mid+1;i<=right;++i) { rSum+=a[i]; if(rSum>tmpRMax) { tmpRMax = rSum; } } int overMax = tmpLMax+tmpRMax; int lMax = MaxSubSeqSum(a,left,mid); int rMax = MaxSubSeqSum(a,mid+1,right); return max(max(overMax,lMax),rMax);}動態規劃的方法就太巧妙了，巧就巧在它掃描時會跟蹤序列上升還是下降的趨勢，從而把前面不適合的部分都給拋棄了，就一路走一路拋，并且同時把合適的記憶住了。
int MaxSubSeqSum2(int a[],int len){ int tmpSum=0,maxSum = 0; for(int i=0;i<len;++i) { tmpSum+=a[i]; if(tmpSum>maxSum) { maxSum = tmpSum; } else if(tmpSum<0) { tmpSum=0; } } return maxSum; }
全站熱搜
留言列表
