題目說明
給定一個整數(shù)數(shù)組 nums 沦辙，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素）乓诽，返回其最大和纸厉。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大底哥，為 6莽囤。
進(jìn)階:
如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法谬擦，嘗試使用更為精妙的分治法求解。
題目鏈接：53. 最大子序和
動態(tài)規(guī)劃分析
0. 如何識別使用動態(tài)規(guī)劃解題
題目求最大和朽缎，屬于求最值惨远、最優(yōu)解的問題。
1-2. 定義狀態(tài)及狀態(tài)轉(zhuǎn)移方程
按照常規(guī)的動態(tài)規(guī)劃思路话肖，一般是這樣定義狀態(tài) dp[i] 的：
dp[i] = nums[0...i] 中的「最大的子數(shù)組和」
按照這個定義北秽，無法由 dp[i] 推導(dǎo) dp[i+1]，因?yàn)轭}目求的最大和的子數(shù)組是連續(xù)的最筒，而狀態(tài)描述的是 nums[0...i] 中的「最大的子數(shù)組和」贺氓，因此要重新定義狀態(tài)：
dp[i] = 以 nums[i] 為結(jié)尾的「最大的子數(shù)組和」
使用數(shù)學(xué)歸納法來找狀態(tài)轉(zhuǎn)移方程：假設(shè)已經(jīng)算出 dp[i-1] ，如何推導(dǎo)出 dp[i] 呢床蜘？
當(dāng)子數(shù)組遇到數(shù)字 nums[i] 時辙培，有兩種選擇：要么把 nums[i] 合并到子數(shù)組中；要么把 nums[i] 作為新的子數(shù)組邢锯；求這兩種選擇中的最大值扬蕊，即為 dp[i] ，因此得到狀態(tài)轉(zhuǎn)移方程：
dp[i] = max(dp[i-1] + nums[i], nums[i])
3. 狀態(tài)初始化
- 當(dāng) nums 為空時丹擎，返回0壶愤。
- 當(dāng) nums 只有一個元素時纺非，返回 nums[0]
即 dp[0] = nums[0]盼忌。
4. 結(jié)果輸出
這里的結(jié)果輸出不再是常規(guī)的 dp[n] 了，而是在遍歷過程中找到最大值庶骄。
5. 空間優(yōu)化
通過狀態(tài)轉(zhuǎn)移方程可知，dp[i] 只與前一個狀態(tài) dp[i-1] 有關(guān)践磅，可以進(jìn)行狀態(tài)壓縮单刁，降低空間復(fù)雜度為 O(1) 。
代碼實(shí)現(xiàn)
func maxSubArray(nums []int) int {
if len(nums) == 0 {
return 0
}
pre, m := nums[0], nums[0]
for i := 1; i < len(nums); i++ {
pre = max(pre+nums[i], nums[i])
if pre > m {
m = pre
}
}
return m
}
func max(x int, y int) int {
if x > y {
return x
}
return y
}
- 時間復(fù)雜度：O(n)府适，遍歷一次數(shù)組羔飞。
- 空間復(fù)雜度：O(1)
