标签（空格分隔）： 动态规划 分治法
传送门：53. 最大子序和。
给定一个整数数组
nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
分析：
总结：分类讨论的标准是：若之前的和小于 0，则将最大和置为当前值，否则计算最大和。
思路1：动态规划
下面展示了标准的动态规划的写法。
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);
}
}
这道题主要就在状态的定义上要思考一下，这里题目中的关键字是“连续”，所以如果我们定义的状态就是题目要求的结果：dp[i] 表示 nums 在区间 [0,i] 中连续子数组的最大和，那么在思考状态转移方程的时候，dp[i] 之前的，例如 dp[i-1] 就有可能是是更前面的连续子数组的最大和，不利于我们分类讨论。
因此，我们可以定义状态：dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。
这样定义状态，分类讨论就变得容易多了，因为 dp[i-1] 表示一定以 nums[i-1] 结尾，那么 dp[i] 就可以有两种情况：
1、把 nums[i] 直接接在 dp[i-1] 表示的那个数组的后面；
例如，dp[i-1] = 3，nums[i] = 5，当然接在后面，越接越大。
2、单独的一个 nums[i] 。
这种情况也比较好想到，比如：dp[i-1] = -3，nums[i] = 5，加上前面的数反而我越来越小了，干脆我另起炉灶吧。
以上两种情况的最大值就是 dp[i] 的值。
最后不要忘记了，最终的结果应该是把所有的 dp[0]，dp[1]，……，dp[n-1] 都看一遍，求最大值。
重点：动态规划问题。状态是：以当前数字为结尾的连续子数组的最大和。
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])
# 最后不要忘记拉通求一遍最大值，或者在上面遍历的时候，就保存最大值
return max(dp)
或者你可以在遍历的时候，就把最大值求出来。
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = len(nums)
if l == 0:
return 0
# 以索引 i 结尾的最大子数组的和
end_i_max = nums[0]
# 最后返回的数
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：分治法
参考资料：连续子数组最大和
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] 元素的最大连续子数组的和
思路是看看左边扩散到底，得到一个最大数
右边扩散到底得到一个最大数
: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)
（本节完）
