原题
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.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
讲解
动态规划
视频@ 哔哩哔哩 动态规划 or YouTube 动态规划
通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划的性质
- 最优子结构（optimal sub-structure）：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
- 重叠子问题（overlapping sub-problem）：动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
状态转移方程
dp[i] = max(nums[i], nums[i] + dp[i - 1])
解释
- i代表数组中的第i个元素的位置
- dp[i]代表从0到i闭区间内，所有包含第i个元素的连续子数组中，总和最大的值
nums = [-2,1,-3,4,-1,2,1,-5,4]
dp = [-2, 1, -2, 4, 3, 5, 6, 1, 5]
时间复杂度
O(n)
参考
代码（C++）
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// boundary
if (nums.size() == ) return ;
// delares
vector<int> dp(nums.size(), );
dp[] = nums[];
int max = dp[];
// loop
for (int i = ; i < nums.size(); ++i) {
dp[i] = nums[i] > nums[i] + dp[i - ] ? nums[i] : nums[i] + dp[i - ];
if (max < dp[i]) max = dp[i];
}
return max;
}
};
分治策略
视频@ 哔哩哔哩 分治策略 or YouTube 分治策略
分治算法是一个解决复杂问题的好工具，它可以把问题分解成若干个子问题，把子问题逐个解决，再组合到一起形成大问题的答案。
这个技巧是很多高效算法的基础，如排序算法（快速排序、归并排序）
实现方式
循环递归
在每一层递归上都有三个步骤：
- 分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
- 解决：若子问题规模较小且易于解决 时，则直接解。否则，递归地解决各子问题。
- 合并：将各子问题的解合并为原问题的解。
注意事项
- 边界条件，即求解问题的最小规模的判定
示意图
递归关系式
T(n) = 2T(n/2) + n
可以利用递归树的方式求解其时间复杂度（其求解过程在《算法导论》中文第三版 P51有讲解）
时间复杂度
O(nlgn)
代码（C++）
class Solution {
public:
int maxSubArray(vector<int>& nums) {
return find(nums, 0, nums.size() - 1);
}
int find(vector<int>& nums, int start, int end) {
// boundary
if (start == end) {
return nums[start];
}
if (start > end) {
return INT_MIN;
}
// delcare
int left_max = 0, right_max = 0, ml = 0, mr = 0;
int middle = (start + end) / 2;
// find
left_max = find(nums, start, middle - 1);
right_max = find(nums, middle + 1, end);
// middle
// to left
for (int i = middle - 1, sum = 0; i >= start; --i) {
sum += nums[i];
if (ml < sum) ml = sum;
}
// to right
for (int i = middle + 1, sum = 0; i <= end; ++i) {
sum += nums[i];
if (mr < sum) mr = sum;
}
// return
return max(max(left_max, right_max), ml + mr + nums[middle]);
}
};