小旭讲解 LeetCode 53. Maximum Subarray 动态规划 分治策略
原题
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]);
}
};
原题：https://leetcode.com/problems/maximum-subarray
文章来源：胡小旭 => 小旭讲解 LeetCode 53. Maximum Subarray
最新文章
- TypeScript 素描-基础类型
- tab+tab
- [转]backbone.js 示例 todos
- 使用CodeSmith快速生成映射文件和映射类
- POJ 3461 Oulipo(字符串匹配，KMP算法)
- 好的git教程
- day01-day04总结- Python 数据类型及其用法
- asp.net 2.0 Session丢失问题
- 0_Simple__matrixMul + 0_Simple__matrixMul_nvrtc
- 腾讯云存储专家深度解读基于Ceph对象存储的混合云机制
- [Swift]LeetCode204. 计数质数 | Count Primes
- MySQL通过Navicat实现远程连接的过程
- lnmp mysql远程访问设置
- Servlet的5种方式实现表单提交
- Revit API根据参数类型取得参数的值
- 8个对程序员来说有用的jQuery小贴士和技巧
- Java多线程学习(一)
- 用 S5PV210 学习 Linux （一） 刷机（一）
- 【zTree】zTree展开树节点
- 重新=》easyui DataGrid是否可以动态的改变列显示的顺序