你好，我是goldsunC

讓我們一起進步吧！

最大子序列和

Question：給定整數(shù)(可能有負數(shù))，求的最大值(為方便起見，如果所有整數(shù)均為負數(shù)，則最大子序列和為0)。

示例：IN????:???[-2,11,-4,13,-5,-2]
OUT????:???20??即從A2-A4

暴力求解

第一種思路很簡單，暴力求解。從數(shù)組第一個整數(shù)開始遍歷每一種長度的最大值，然后遍歷之后的最大值即是最大子序列和，如果最大值為負數(shù)則初始化為0，例如：指定數(shù)組為：[-2,11,-4,13,-5,-2]首先初始化最大值為-2，因為-2為負數(shù)所以最大值為0，然后計算-2+11，然后更新最大值為9，然后計算-2+11-4，保持當(dāng)前最大值，然后計算-2+11-4+13，更新最大值為18，一直加到數(shù)組最后一位數(shù)，再從11開始求最大值，然后再從-4開始，就這樣把數(shù)組每一種子序列和都遍歷了，求得最大值。源碼(Java)：public?class?maxValueSum?{
????public?static?void?main(String[]?args)?{
????????int[]?array?=?{-2,11,-4,13,-5,-2};
????????System.out.println(Max(array));
????}
????public?static?int?Max(int[]?array)?{
????????int?maxnum?=?array[0];
????????for?(int?i=0;i????????????int?currentnum?=?0;
????????????for?(int?j=i;j????????????????currentnum?+=?array[j];
????????????????if?(currentnum>maxnum)
????????????????????maxnum?=?currentnum;
????????????}
????????}
????????return?maxnum;
????}
}
源碼(Python)：def?Max(array)?:
????maxnum?=?0
????for?i?in?range(len(array)):
????????num?=?0
????????for?j?in?range(i,len(array)):
????????????num?+=?array[j]
????????????if?num?>?maxnum:
????????????????maxnum?=?num
????return?maxnum
array?=?[-2,11,-4,13,-5,-2]
print(Max(array))
上面暴力求解法很簡單，但是有個突出的問題，就是時間復(fù)雜度為O()，當(dāng)涉及到大量輸入的時候，效率非常低。

分治+遞歸求解

通常來講，我們遇見遞歸的時候往往伴隨的還有很高的時間復(fù)雜度，但對于這個問題來講還有一個使用遞歸+分治實現(xiàn)的稍微復(fù)雜的方法，其時間復(fù)雜度卻僅為O()，或許這個算法就是體現(xiàn)遞歸為例的最好范例了。這個算法使用一種"分治"的策略，其想法是把問題分成兩個大致相等的子問題，然后采用遞歸對他們求解，這是分，治是將兩個子問題的解合并到一起并再做些少量的附加工作，最后得到整個問題的解。假如將傳入的數(shù)組從中間分成左右兩個部分，例如：[-2,11,-4,13,-5,-2]->[-2,11,-4]和[13,-5,-2]那么問題的解可能出現(xiàn)在三處出現(xiàn)：

左半部分[-2,-11,-4]

右半部分[13,-5,-2]

或者橫跨兩個部分，它一定包括左半部分的最后一個值和右半部分的第一個值。

對上述問題求解得：左半部分的最大值為11，右半部分的最大值為13，而橫跨這兩個部分包含左半部分最后一個值以及右半部分第一個值的最大值為20，即11-4+13，將三者對比，則返回最大值20。而這個時候我們求各部分最大值是直接看出來的，那實際應(yīng)該怎么求呢？機器可看不出來，只能靠算法求解。那怎么求？用剛才講過的暴力求解?那樣的話我們分這一次沒有意義，因此我們需要遞歸地繼續(xù)分下去。看一下算法源碼(Java)：public?class?maxVlaueSum2?{
????public?static?void?main(String[]?args)?{
????????//?初始化數(shù)組
????????int[]?array?=?{-2,11,-4,13,-5,-2};
????????System.out.println(maxSum(array,0,array.length-1));
????}

????/**
?????*?遞歸求解函數(shù)
?????*?@param?array ：傳入要解決的數(shù)組
?????*?@param?left ?：要解決子問題的左界
?????*?@param?right ：要解決子問題的右界
?????*?@return??：返回三個部分的最大值
?????*/
????public?static?int?maxSum(int[]?array,int?left,int?right)?{
????????//?? BASE情況，如果遞歸到了最后一層，那么返回合適的值，小于0返回0，大于0返回該數(shù)。
????????if(left?==?right)?{
????????????if?(array[left]?>?0)
????????????????return?array[left];
????????????else?return?0;
????????}
????????int?center?=?(left+right)/2;????//??取得數(shù)組中點
????????int?leftSubSUM?=?maxSum(array,left,center);?????//??子問題左半部分最優(yōu)解
????????int?rightSubSUM?=?maxSum(array,center+1,right);?????//??子問題右半部分最優(yōu)解

????????int?leftNowSum?=?0,?maxleftSum?=?0;?????//??當(dāng)前問題左半部分等待求和的當(dāng)前值以及最大值

????????//??遍歷求包含左半部分最后一個值的最大值
????????for?(int?i=center;i>=left;i--)?{
????????????leftNowSum?+=?array[i];
????????????if?(leftNowSum?>?maxleftSum)?{
????????????????maxleftSum?=?leftNowSum;
????????????}
????????}
????????int?rightNowSum?=?0,maxrightSum?=?0;????//??當(dāng)前問題右半部分等待求和的當(dāng)前值以及最大值

????????//??遍歷求包含右半部分的第一個值的最大值
????????for?(int?j=center+1;j<=right;j++)?{
????????????rightNowSum?+=?array[j];
????????????if?(rightNowSum>maxrightSum)?{
????????????????maxrightSum?=?rightNowSum;
????????????}
????????}
????????//??返回當(dāng)前問題的左半部分最大值、右半部分的最大值和橫跨兩部分最大值的最大值。即為當(dāng)前問題的解。
????????return?Math.max(Math.max(leftSubSUM,rightSubSUM),(maxleftSum+maxrightSum));
????}
}
源碼(Python)：def?maxSUM(array,left,right):
????if?left==right:
????????if?array[left]?>?0:
????????????return?array[left]
????????else:
????????????return?0
????center?=?int((left+right)/2)
????leftSubSUM?=?maxSUM(array,left,center)
????rightSubSUM?=?maxSUM(array,center+1,right)

????leftNowNum,maxleftSum?=?0,0
????for?i?in?reversed(range(left,center+1)):
????????leftNowNum?+=?array[i]
????????if?leftNowNum?>?maxleftSum:
????????????maxleftSum?=?leftNowNum

????rightNowNum,maxrightSum?=?0,0
????for?i?in?range(center+1,right+1):
????????rightNowNum?+=?array[i]
????????if?rightNowNum?>?maxrightSum:
????????????maxrightSum?=?rightNowNum
????return?max(leftSubSUM,rightSubSUM,maxleftSum+maxrightSum)
if?__name__?==?'__main__':
????array?=?[-2,11,-4,13,-5,-2]
????print(maxSUM(array,0,len(array)-1))
兩個程序的原理相同，運行正確，不過鄙人水平有限，如果各位發(fā)現(xiàn)有問題還煩請指出，謝謝！這個算法稍微復(fù)雜一點，程序更長一點，不過時間復(fù)雜度只有O()，相比O()已經(jīng)好了很多，不過事實上還有一種更加有效且巧妙的算法。

算法3

這個算法我也不清楚它的名字，不過它確是最好的，首先看源代碼：源碼(Java)：public?class?maxValueSum3?{
????public?static?void?main(String[]?args)?{
????????int[]?array?=?{-2,11,-4,13,-5,-2};
????????System.out.println(maxSubSum(array));
????}
????public?static?int?maxSubSum(int?[]?array)?{
????????int?maxSum?=?0,NowSum?=?0;
????????for?(int?i?=?0;?i?????????????NowSum?+=?array[i];

????????????if?(NowSum?>?maxSum)
????????????????maxSum?=?NowSum;
????????????else?if?(NowSum?0)
????????????????NowSum?=?0;
????????}
????????return?maxSum;
????}
}
源碼(Python)：def?maxSubSum(array):
????maxSum,NowSum?=?0,0
????for?i?in?range(len(array)):
????????NowSum?+=?array[i]
????????if?NowSum?>?maxSum:
????????????maxSum?=?NowSum
????????elif?NowSum?0:
????????????NowSum?=?0
????return?maxSum
if?__name__?==?'__main__':
????array?=?[-2,11,-4,13,-5,-2]
????print(maxSubSum(array))
代碼很短，不過要想清楚原理可能比之前都稍微難點。它是正確可行的，并且不難看出時間復(fù)雜度為O(N)，它的效率很高，不過到底是怎么實現(xiàn)的呢？那寧哥我就用蹩腳的話來簡單分享下我的理解吧。首先可以看到，該算法只是簡單遍歷了一遍數(shù)組而已，就找到了最大子序列和。為什么可以這樣？首先，任何負的子序列不可能是最優(yōu)子序列的前綴。除非數(shù)組中的所有值均為負數(shù)，只要有一個正數(shù)，那么最優(yōu)子序列的和的前綴一定不可能是負數(shù)。因此這也就說明了代碼中的else if(NowSum<0) NowSUm=0;了，也就是如果當(dāng)前子序列的和為負值，那么初始化為0，它已經(jīng)不可能是最有子序列的前綴了，就把它的記錄拋棄了，如果當(dāng)前位置在N，那問題就變成了求array[N+1]-array[array.length-1]的最有子序列了。然后還有一個判斷語句if(NowSum > maxSum) maxSum = thisSum;，看起來很簡單，意思就是如果當(dāng)前子序列和大于記錄的最大值，那就更新。可如果放到整個程序里如何保證能正確運行呢？對一個子序列，如果是每一個數(shù)都遞增或者遞減比較好理解，遞增的話最大子序列值就是從第一個大于0的數(shù)開始到整個序列，如果是遞減的話就是第一個數(shù)開始到第一個小于等于0之前的那個數(shù)。還有兩種情況，子序列整體遞增或整體減小，但是數(shù)大大小小不確定。如果子序列整體是增加的，也好理解，仍然是整個序列值唄，那如果子序列是整體遞減呢？如果整體是遞減的，說明剛開始某個地方會有一個最大值，那樣的話我們的方法在剛開始就已經(jīng)把序列最大值記錄了，后面只是更新而已，哈哈哈突然解決。明白了嗎？

???end???

走在路上

goldsunC

總結(jié)

以上是生活随笔為你收集整理的c 最大子序列和_最大子序列和暴力法、分治+递归法、妙法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。