# 题目描述

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

Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

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

# 我的解法

## 实现代码

Runtime: 308 ms, faster than 5.00% of C++ online submissions for Maximum Subarray.
Memory Usage: 9.2 MB, less than 99.02% of C++ online submissions for Maximum Subarray.

# 一次遍历

Runtime: 4 ms, faster than 98.58% of C++ online submissions for Maximum Subarray.
Memory Usage: 9.1 MB, less than 100.00% of C++ online submissions for Maximum Subarray.

# 动态规划

• 最优子问题：如果一个问题的最优解包含了其中子问题的最优解，那么称其有最优子结构
• 重叠子问题：当解决一个问题时，往往依赖其更小规模的子问题的解，甚至依赖与若干个规模更小的子问题的解。

• 最优子问题：很明显对于最大的子集最优子问题是符合的
• 重叠子问题：对于当前的解，需要用到之前子集求出来的解（感觉有点解释不清楚）

1. [-2]的最大子集显然就是它自己本身，所以dp=[-2]
2. [-2,1]的子集有{-2,-1,1}，最大子集就是1了，dp=[-2,1]
3. 对于[-2,1,-3]，上一个子集的解是1，加上-3为-2，dp=[-2,1,-2]

Runtime: 4 ms, faster than 98.60% of C++ online submissions for Maximum Subarray.
Memory Usage: 9.5 MB, less than 9.80% of C++ online submissions for Maximum Subarray.