下午真的很想睡覺，可是上床，下床好幾次了，都沒睡著，焦慮啊！！可能像我這樣剛畢業的人都會這樣！工資好像還沒發！我問他們，他們說其他人都發了。。。馬上又要交房租了，我想對房東說，我已經打到你卡上了，你沒收到嗎？然后我就去露宿街頭。。。我很勇敢，但是我不傻！
給定n個整數（可能為負）組成序列a1,a2,...an，求該序列的最大和子段！這個題目有很多解法！！！
一、窮舉法
這種方法很容易想到，就不怎么說明了，直接上代碼！
代碼如下：
int MaxSum(int n,int *a,int &besti,int& bestj)
{
int sum=0;
int i,j;
for(i=1;i<=n;i++)
{
int thissum=0;
for(j=i;j<=n;j++)
{
thissum+=a[j];
if(thissum>sum)
{
sum=thissum;
besti=i;
bestj=j;
}
}
}
return sum;
} 二、二分法
將數組a[1..n]分成左右的兩段a[1..n/2]和a[n/2+1...n]；最大和字段可能落在左子段，可能落在右子段，也可能落在中間，即一部分在左，一部分在右；對于前面兩種情況可以直接遞歸求解，對于最后這種情況，只要從a[n/2]出發，分別累加左子段和得到一個最大值s1，右子段和得到一個最大值s2，s1+s2可得到一個最優值；然后取三者最優！！
代碼如下：
int MaxSubSum(int *a,int left,int right)
{
int sum=0;
int j,i;
if(left==right) sum=a[left]>0?a[left]:0;
else
{
int center=(left+right)/2;
int leftsum=MaxSubSum(a,left,center);
int rightsum=MaxSubSum(a,center+1,right);
int s1=0;
int lefts=0;
for(i=center;i>=left;i--)
{
lefts+=a[i];
if(lefts>s1)
s1=lefts;
}
int s2=0;
int rights=0;
for(j=center+1;j<=right;j++)
{
rights+=a[j];
if(rights>s2)
s2=rights;
}
sum=s1+s2;
if(sum<leftsum) sum=leftsum;
if(sum<rightsum) sum=rightsum;
}
return sum;
}
其實這個算法先將n大的序列二分置大小為1的序列，然后回溯回去，回溯過程中一直取最優值，實現了信息填充和附帶功能！
三、動態規劃
這種算法最簡單，效率也最高，但是不是很容易理解！好的東西常常很難去解釋！
我個人是這么理解的，假設最大序列是從第一個數開始加的一個子序列，那么我們只要從第一個數一直加，取最大的那個值解釋最優了！當然這只是假設，最大子序列的初始位置可能會在其他地方，這里就有一個舍棄和，和重新累加的問題，假設從1開始加我們得到一個正和，我們就舍棄（當然在這個過程中我們會一直比較最優值，并把它記錄下來），重新累加，顯然，無論后面累加得到一個正和或者負和我們都應該把前面那個舍棄的正和加進去；類似的當從1累加得到非正數時，我們就應該把它這段累加和舍棄，重新開始累加！
代碼如下：
//求一維數組最大和子段 不考慮數組全為負的情況
int maxsum(int n,int *a)
{
int sum=0,b=0;
int i;
for(i=1;i<=n;i++)
{
if(b>0)
b+=a[i];
else
b=a[i];
if(b>sum) sum=b;
}
return sum;
}
最終其實會得到一幅以數列為軸的點圖，最高那個就是最大和字段和！
posted on 2010-09-05 17:29
jince 閱讀(575)
評論(2) 編輯 收藏 引用 所屬分類:
算法設計與分析