子數列可能是[-2],[2,-3],[-5,3]
要如何知道最大和的子數列呢?
如果選擇從頭到尾一個加一個來做比較
那這樣的時間複雜度為O(n^2)
如果我們是用動態規劃來解決
做法為
當我們判斷值是否加入數列時
拿值前面的最佳解 + 值 和值本身做比較
如果加起來比較大 值就加入子數列
反之 值自身當作由首至此的最佳解
公式
dp[i] = max(n[i],dp[i - 1] + n[i])
===進入例子===
[−2,2,−3,4,−1,2,1,−5,3]
第一個數不拿來做比較 因為它前面沒有值
最佳解即是本身
[-2,x,x,x,x,x,x,x,x]
第二個數 2
2 與 -2 + 2 做比較
2 > 0
加了會變成0 不加則是2
所以選擇不加
[-2,2,x,x,x,x,x,x,x]
第三個數 -3
-3 與 2 + (-3) 做比較
-3 < -1
加了會變成-1 不加則是-3
所以選擇加入
[-2,2,-1,x,x,x,x,x,x]
第四個數 4
4 與 (-1) + 4 做比較
4 > 3
加了會變成3 不加則是4
所以選擇不加
[-2,2,-1,4,x,x,x,x,x]
.
.
.
.
以此類推 判斷加入與否
最後得到 [-2,2,-1,4,3,5,6,1,4]
子數列最大和為 6 ([4,−1,2,1])
def findMaxSubarray(A):
max_left = 0
max_right = 0
max_sum = A[0]
for i in range(1,len(A)):
if A[i] > A[i] + A[i - 1]:
max_right = i
max_left = i
max_sum = A[i]
else:
if A[i] + A[i - 1] > max_sum:
max_right = i
max_sum = A[i] + A[i - 1]
A[i] = A[i] + A[i - 1]
return max_left,max_right,max_sum
完
reference: https://www.itread01.com/content/1541564489.html
創作內容
動態規劃 最大子數列問題
☆活動☆ (32)