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