Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

4/3/2019 二周目 DP

DP就是要把大问题分解小问题，找到每个小问题的最优解，再从这些解里面找到最优解。

my codE in cpp

• 开始误将num和_max比较，导致漏掉后面的最大子序列。应该将num和sum比较，找到subpro最大的子序列。
• 因为最大子序列可能是分散的，求得每个最大子序列的和记为sum，在从这些sum中找到最大的和。
• O(n) time

Divide and Conquer

1. 二分法，分别求左右两边的最大序列和，不包含中点。
2. 从中间开始，一直到两边端点，累计总和，记下分别到两边端点的最大和，包含中点。
3. 比较二分的最大值 与 包含中点的最大值，哪个更大。

3/15/2019 一周目

Divide and Conquer

• The Divide-and-Conquer algorithm breaks nums into two halves and find the maximum subarray sum in them recursively.
• the maximum subarray spans the two halves.
• a linear algorithm: starting from the middle element and move to both ends (left and right ends), record the maximum sum we have seen. In this case, the maximum sum is finally equal to the middle element plus the maximum sum of moving leftwards and the maximum sum of moving rightwards.
• Since we are done with LHS and RHS, we only need to check the case where we pass the middle element.(i.e. the middle element must be included).In that case, since our question asks a continuous subset, it must expand that way.

2*O(n/2)+O(1)=O(n)

• divide：用递归来分别求左右子集的max
• merge:用dp来从左右分别线性探索，加上mid
• 最后找到divide和merge中最大的就是要求的值。

LC in cpp

Thanks for Support.