最大m個子段和，問題規(guī)模從1個子段和擴展到m個，動態(tài)規(guī)劃

問題規(guī)模由2個決定，一是子段數(shù)m,二是元素個數(shù)n,準確的說是最后一個子段終止的標號

b(i,j)定義為：前j個元素中有i個子段，且第i個子段包含j,i個子段和為b(i,j)
那么原問題的最優(yōu)解為max{b(m,j)},m<=j<=n
還是不是針對原問題動態(tài)規(guī)劃，動態(tài)規(guī)劃的問題是可能解，最后在可行解里面找最優(yōu)解

根據(jù)b(i,j)定義，有兩種情況，第一種情況arr[i]是第i個子段的一部分,那前面j-1的尾巴也是屬于第i個子段，可以把前面j-1也看成有i個子段，即b(i,j-1) + arr[j];另外一種情況arr[i]就是第i個子段的全部，也就是前面j-1的尾巴不屬于第i個子段，那我們必須在前j-1個元素里找到i-1個子段使之和最大（類似原始問題max{b(m,j)},m<=j<=n），所以我們這里是max{b(i-1,k)},i-1<=k<=j-1,即第二種情況為：max{b(i-1,k)} + arr[j] ,i-1<=k<=j-1

狀態(tài)方程為：

代碼實現(xiàn)如下：

#%% def maxMSum(arr,m):n = len(arr)b = np.zeros((m+1,n+1),int)for i in range(1,m+1):# (i,n+1-m+i),本來是(i,n+1），可以發(fā)現(xiàn)有些沒有必要計算，# 因為[i][j]總是取左邊或者左上的數(shù)據(jù) for j in range(i,n+1-m+i):# 最后剛好子段個數(shù)==元素個數(shù)時，就是相當于一個元素一個子段if j == i:b[i][j] = b[i-1][j-1] + arr[j-1] # 其他的情況需要按照狀態(tài)方程比較else:# 第一種情況b[i][j] = b[i][j-1] + arr[j-1]# 第二種情況for k in range(i-1,j):if b[i-1][k] + arr[j-1] > b[i][j]:b[i][j] = b[i-1][k] + arr[j-1]# 最后一行都是可行解，取最大為最優(yōu)解return b,max(b[m][:])arr = [-2,11,-4,-4,13,-5,-2,1,1,5,8,-1] print(maxMSum(arr,3)) (array([[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[ 0, -2, 11, 7, 3, 16, 11, 9, 10, 11, 16, 0, 0],[ 0, 0, 9, 7, 7, 24, 19, 17, 18, 19, 24, 32, 0],[ 0, 0, 0, 5, 5, 22, 19, 22, 25, 26, 31, 39, 38]]), 39)

從代碼或者從狀態(tài)方程我們可以看出

只是使用了兩行b[i-1][:j]和b[i][j-1]數(shù)據(jù)，可以利用滾動數(shù)組優(yōu)化，如何優(yōu)化了？從這里看至少需要2行才行。

b[i-1][:j]用于求max{b(i-1,k)} + arr[j]，我們可以使用一個數(shù)組c專門記錄max{b(i-1,k)} ，c[j-1]代表k從i-1到j-1里面最大值，b[i][j-1]直接使用當前的數(shù)組b[j-1]就行了,當前行b[j] = max{c[j-1],b[j-1]} + arr[j], 此時還需要做一件事，時刻記錄b到目前位置j的最大值，把b當前最大值cur_max一直放在空中，一旦得到一個新的b大于空中的值的話更新空中的值cur_max，這個值代表的時0到j的最大值，把更新之前的cur_max放到c[j-1]（記住這一層b[j+1]待會兒用的是c[j]），留給下一層也就是i+1層使用，i+1層的b[j] 用的是上一層留下的c[j-1]。

這樣使用滾動數(shù)組節(jié)約了空間消費，使用臨時cur_max一輪比較就把一行的最大值都更新了，避免后續(xù)每一次都用for循環(huán)算一遍。

代碼實現(xiàn)如下：

def maxMSum_opt(arr,m):n = len(arr)b = [0]*(n+1)# 數(shù)組c專門記錄max{b(i-1,k)} ，c[j-1]代表k從i-1到j-1里面最大值，需要初始化# 參考b的第0行可以得到c的初始化如下c= [0]*(n+1)for i in range(1,m+1):# 先把第一個元素處理一下，也就是j == i，我們只使用一個一維的滾動數(shù)組b[i] = b[i-1] + arr[i-1]# 我們需要一個變量記錄當前一行的到當前位置的最大值cur_max = b[i]# (i,n+1-m+i),本來是(i,n+1），可以發(fā)現(xiàn)有些沒有必要計算，# 因為[i][j]總是取左邊或者左上的數(shù)據(jù) # 第一個元素上面已經(jīng)處理了for j in range(i+1,n+1-m+i):# 獲取b[j]當前的值b[j] = max(b[j-1],c[j-1]) + arr[j-1]# c[j-1] 使用了之后，就要更新c[j-1]留給下一層使用，值為還未更新的cur_maxc[j-1] = cur_max# 更新后的cur_max要放在c[j]，但是舊的c[j]還沒使用了，所以c[j]的更新是滯后一步的if cur_max < b[j]:cur_max = b[j]# 我們會發(fā)現(xiàn)內(nèi)存循環(huán)完了，最后的cur_max還沒更新到c里面，因為c的更新是滯后一步# 得再次進入循環(huán)才能更新的，注意這里c的標號c[n-m+i] = cur_max# 最后一行都是可行解，取最大為最優(yōu)解return b,max(b[:])arr = [-2,11,-4,-4,13,-5,-2,1,1,5,8,-1] print(maxMSum_opt(arr,3)) ([0, -2, 9, 5, 5, 22, 19, 22, 25, 26, 31, 39, 38], 39) 與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的算法优化：最大m个子段和，问题规模从1个子段和扩展到m个，动态规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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