有這一道題，計(jì)算給定字符串中最大子符串的和频鉴，如 10 ，-2 ，3相恃，4返回其最大子串的和，思路丸升，假設(shè)這個(gè)子串第i位的和為dp[i]界赔，則第i-1位的和為 dp [i-1]
最大子序和
給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）雏吭，返回其最大和锁施。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6杖们。
題目分析
先說(shuō)下我之前的復(fù)雜思路：因?yàn)閿?shù)組中可能有正有負(fù)悉抵，先將連續(xù)正、或連續(xù)負(fù)的數(shù)合并摘完，這樣列表如果全正姥饰、最大和為數(shù)組和；如果列表全負(fù)孝治、最大和為最大的單項(xiàng)值列粪；如果有正有負(fù)、合并后就會(huì)正負(fù)相間谈飒，通過(guò)比較相鄰正負(fù)相加后的結(jié)果來(lái)判斷是否計(jì)入最大和中岂座。
聽著很繞，實(shí)施起來(lái)也不簡(jiǎn)單杭措，費(fèi)白天功夫费什、通過(guò)各種特例補(bǔ)全了整個(gè)代碼思路。接下來(lái)我們對(duì)比看下動(dòng)態(tài)規(guī)劃的設(shè)計(jì)手素。
首先要設(shè)計(jì)狀態(tài)鸳址，dp [ i ] 我們定義為以數(shù)組 nums [ i ] 結(jié)尾的連續(xù)子數(shù)組的最大和——可能我們會(huì)有疑問(wèn)赘那，這個(gè)狀態(tài)怎么找的？注意氯质，動(dòng)態(tài)規(guī)劃最關(guān)鍵的就是找準(zhǔn)狀態(tài)和狀態(tài)轉(zhuǎn)移方程募舟，如何找準(zhǔn)這個(gè)要么憑理論分析、要么就是多做題積累經(jīng)驗(yàn)闻察。這也是我們翻看很多講解拱礁、分析老是說(shuō)動(dòng)態(tài)規(guī)劃不難、很簡(jiǎn)單的原因：因?yàn)槿思业姆e累和經(jīng)驗(yàn)在那擺著辕漂，見怪不怪了呢灶，對(duì)于剛接觸這類題型的我們就好奇寶寶似的滿腦袋問(wèn)號(hào)。如果還記得昨天做過(guò)的背包問(wèn)題钉嘹，也是定義了類似在 i 位置的背包最大價(jià)值鸯乃，這里定義要以 i 位置結(jié)尾的子數(shù)組，就是為了可以和 dp [ i-1 ] 建立直接聯(lián)系跋涣。
有了上面的狀態(tài)定義缨睡，找狀態(tài)轉(zhuǎn)移方程就會(huì)輕松些，在計(jì)算 dp[ i ] 時(shí)陈辱，我們可以拿到的有以 nums[i-1] 項(xiàng)結(jié)尾的子數(shù)組的最大和 dp[i-1] 和 nums[ i ]奖年。根據(jù)狀態(tài)定義，以 nums[i] 結(jié)尾的子數(shù)組沛贪，那么計(jì)算和一定有 nums[i] 參與陋守，再看之前的項(xiàng)，倘若 dp[i-1] 為負(fù)利赋，那么最大和就不必添加這部分水评；但如果其為正，則將其加入進(jìn)來(lái)即可媚送。完畢~
是的中燥，這就完事了，上代碼季希。
代碼實(shí)現(xiàn)
class Solution:
? ? def maxSubArray(self, nums: List[int]) -> int:
? ? ? ? n = len(nums)
? ? ? ? # 對(duì)單項(xiàng)數(shù)組單獨(dú)處理
? ? ? ? if n==1:
? ? ? ? ? ? return nums[0]
? ? ? ? # dp[i] 為以 nums[i] 結(jié)尾的連續(xù)子數(shù)組最大和
? ? ? ? dp = [0]*n
? ? ? ? # 初始化 dp 數(shù)組為 n 個(gè) 0 的列表
? ? ? ? dp[0] = nums[0]
? ?
? ? ? ? # 遍歷每一位
? ? ? ? for i in range(1,n):
? ? ? ? ? # dp[i-1]即以 nums[i-1] 結(jié)尾的子數(shù)組最大和
? ? ? ? ? # 如果 dp[i-1] 非正褪那，則不加
? ? ? ? ? ? if dp[i-1]<=0:
? ? ? ? ? ? ? ? dp[i] = nums[i]
? ? ? ? ? ? # 如果正，則加起來(lái)
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? dp[i] = dp[i-1]+nums[i]
? ? ? ? # 返回 dp 記錄列表的最大值
? ? ? ? return max(dp)
因?yàn)槲覀兺ㄟ^(guò)對(duì) n 位數(shù)組的一次遍歷建立了所謂的狀態(tài)列表式塌，最后執(zhí)行了次求最大值運(yùn)輸博敬，整體時(shí)間復(fù)雜度與 n 成線性關(guān)系，即 O(n) 時(shí)間復(fù)雜度峰尝；在整個(gè)過(guò)程中偏窝，額外建立了 dp 這個(gè)長(zhǎng)度為 n 的數(shù)組或列表，空間復(fù)雜度也為 O(n)。
