標(biāo)簽（空格分隔）： 動(dòng)態(tài)規(guī)劃 分治法
傳送門：53. 最大子序和富岳。
給定一個(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。進(jìn)階:
如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法狼电，嘗試使用更為精妙的分治法求解。
分析：
總結(jié)：分類討論的標(biāo)準(zhǔn)是：若之前的和小于 0肩碟，則將最大和置為當(dāng)前值，否則計(jì)算最大和削祈。
思路1：動(dòng)態(tài)規(guī)劃
下面展示了標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃的寫法脑漫。
Java 代碼：
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int n = array.length;
if (n == 0) {
return 0;
}
int[] dp = new int[n];
dp[0] = array[0];
int res = array[0];
for (int i = 1; i < n; i++) {
dp[i] = Integer.max(dp[i - 1] + array[i], array[i]);
res = Integer.max(res, dp[i]);
}
return res;
}
public static void main(String[] args) {
int[] nums = new int[]{6, -3, -2, 7, -15, 1, 2, 2};
Solution solution = new Solution();
int findGreatestSumOfSubArray = solution.FindGreatestSumOfSubArray(nums);
System.out.println(findGreatestSumOfSubArray);
}
}
這道題主要就在狀態(tài)的定義上要思考一下，這里題目中的關(guān)鍵字是“連續(xù)”优幸，所以如果我們定義的狀態(tài)就是題目要求的結(jié)果：dp[i] 表示 nums 在區(qū)間 [0,i] 中連續(xù)子數(shù)組的最大和，那么在思考狀態(tài)轉(zhuǎn)移方程的時(shí)候网杆，dp[i] 之前的，例如 dp[i-1] 就有可能是是更前面的連續(xù)子數(shù)組的最大和碳却，不利于我們分類討論。
因此笑旺，我們可以定義狀態(tài)：dp[i] 表示以 nums[i] 結(jié)尾的連續(xù)子數(shù)組的最大和。
這樣定義狀態(tài)筒主，分類討論就變得容易多了，因?yàn)?dp[i-1] 表示一定以 nums[i-1] 結(jié)尾乌妙，那么 dp[i] 就可以有兩種情況：
1、把 nums[i] 直接接在 dp[i-1] 表示的那個(gè)數(shù)組的后面藤韵；
例如火诸，dp[i-1] = 3，nums[i] = 5奈搜，當(dāng)然接在后面悉盆，越接越大馋吗。
2、單獨(dú)的一個(gè) nums[i] 宏粤。
這種情況也比較好想到，比如：dp[i-1] = -3绍哎，nums[i] = 5，加上前面的數(shù)反而我越來越小了崇堰，干脆我另起爐灶吧沃于。
以上兩種情況的最大值就是 dp[i] 的值。
最后不要忘記了繁莹，最終的結(jié)果應(yīng)該是把所有的 dp[0]，dp[1]咨演，……，dp[n-1] 都看一遍薄风，求最大值饵较。
重點(diǎn)：動(dòng)態(tài)規(guī)劃問題。狀態(tài)是：以當(dāng)前數(shù)字為結(jié)尾的連續(xù)子數(shù)組的最大和村刨。
Python 代碼：
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = len(nums)
if l == 0:
return 0
if l == 1:
return nums[0]
dp = [0 for _ in range(l)]
dp[0] = nums[0]
for i in range(1, l):
dp[i] = max(dp[i - 1] + nums[i], nums[i])
# 最后不要忘記拉通求一遍最大值，或者在上面遍歷的時(shí)候嵌牺，就保存最大值
return max(dp)
或者你可以在遍歷的時(shí)候，就把最大值求出來逆粹。
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = len(nums)
if l == 0:
return 0
# 以索引 i 結(jié)尾的最大子數(shù)組的和
end_i_max = nums[0]
# 最后返回的數(shù)
res = nums[0]
for i in range(1, l):
# 例：[-3,1]
end_i_max = max(nums[i], end_i_max + nums[i])
res = max(res, end_i_max)
return res
思路2：分治法
參考資料：連續(xù)子數(shù)組最大和
Python 寫法：
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
return self.__max_sub_array(nums, 0, n - 1)
def __max_sub_array(self, nums, left, right):
if left == right:
return nums[left]
mid = left + (right - left) // 2
return max(self.__max_sub_array(nums, left, mid),
self.__max_sub_array(nums, mid + 1, right),
self.__max_cross_array(nums, left, mid, right))
def __max_cross_array(self, nums, left, mid, right):
"""
一定包含 nums[mid] 元素的最大連續(xù)子數(shù)組的和
思路是看看左邊擴(kuò)散到底，得到一個(gè)最大數(shù)
右邊擴(kuò)散到底得到一個(gè)最大數(shù)
:param nums:
:param mid:
:param right:
:return:
"""
ls = 0
j = mid - 1
s1 = 0
while j >= left:
s1 += nums[j]
ls = max(ls, s1)
j -= 1
rs = 0
j = mid + 1
s2 = 0
while j <= right:
s2 += nums[j]
rs = max(rs, s2)
j += 1
return ls + nums[mid] + rs
if __name__ == '__main__':
s = Solution()
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result = s.maxSubArray(nums)
print(result)
（本節(jié)完）
