53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
思路
- 这道题是入门级DP，状态方程可以简单理解为，如果一个数加上负数，那么数值肯定会变小。
- 所以在这里，会去判断当前值
nums[i]和当前值加上他的前一个值dp[i - 1] + nums[i]，那个值更大。 - 所以转移方程为
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
方程也可以等价为f(k) = max{ f(k-1), 0 } + nums[k-1]
动态规划
class Solution {
// 动态规划
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int ans = 0;
// 1\. 状态定义
// dp[i] 表示前 i 个元素的最大连续子数组的和
int[] dp = new int[nums.length];
// 2\. 状态初始化，数组中第一个元素的最大和就是第一个元素值
dp[0] = nums[0];
ans = nums[0];
// 3\. 状态转移
// 转移方程：dp[i] = max(dp[i - 1], 0) + nums[i]
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
// 更新最大和
ans = Math.max(ans, dp[i]);
}
return ans;
}
}
以上代码的时间复杂度是 O(N)，空间复杂度也是 O(N)，实际上我们可以降低空间复杂度到 O(1)。
每个状态只与前一个状态有关，所以为了降低空间复杂度只用一个变量来保存,所以可以从DP变到贪心，贪心是特殊的DP。
贪心
- 使用单个数组作为输入来查找最大（或最小）元素（或总和）的问题，贪心算法是可以在线性时间解决的方法之一。
- 每一步都选择最佳方案，到最后就是全局最优的方案。
算法：
该算法通用且简单：遍历数组并在每个步骤中更新：
- 当前元素
- 当前元素位置的最大和
- 迄今为止的最大和
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int currSum = nums[0], maxSum = nums[0];
for(int i = 1; i < n; ++i) {
currSum = Math.max(nums[i], currSum + nums[i]);
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
}
}
复杂度分析
- 时间复杂度：\mathcal{O}(N)O(N)。只遍历一次数组。
- 空间复杂度：\mathcal{O}(1)O(1)，只使用了常数空间。
参考
动态规划的解法
我们要记住动态规划的解题四步骤：
- 定义子问题
- 写出子问题的递推关系
- 确定 DP 数组的计算顺序
- 空间优化（可选）
关于四步骤的基础讲解可以参考在198. 打家劫问题下的题解：图解动态规划的解题四步骤，以经典的打家劫舍问题为例讲解了这四个步骤。 - 图解动态规划的解题四步骤（C++/Java/Python）
