Leetcode53. 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.
解法一 动态规划
第 1 步：定义状态
dp[i]表示以 nums[i] 结尾的连续子数组的最大和。
第 2 步：思考状态转移方程
- 如果
dp[i-1] < 0，那么dp[i] = nums[i]。 - 如果
dp[i-1] >= 0，那么dp[i] = dp[i-1] + nums [i]。
也可以写成dp[i] = max(nums[i], dp[i-1] + nums[i])
第 3 步：思考初始值
dp[0] = nums[0]
第 4 步：思考输出
输出应该是把所有的 dp[0]、dp[1]、……、dp[n - 1] 都看一遍，取最大值。
- 时间复杂度：O(n)
- 空间复杂度：O(n)
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
int max = nums[0];
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
//两种情况更新 dp[i]
if (dp[i - 1] < 0) {
dp[i] = nums[i];
} else {
dp[i] = dp[i - 1] + nums[i];
}
//更新 max
max = Math.max(max, dp[i]);
}
return max;
}
根据“状态转移方程 2”可以将dp[i]的更新改为
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
第 5 步：思考状态压缩
既然当前状态只与上一个状态有关，我们可以将空间复杂度压缩到O(1)
public class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
// 起名叫 pre 表示的意思是“上一个状态”的值
int pre = nums[0];
int res = pre;
for (int i = 1; i < len; i++) {
pre = Math.max(nums[i], pre + nums[i]);
res = Math.max(res, pre);
}
return res;
}
}
解法二 分治
maxSubArraySum(int[] nums, int left, int right)能得到 num[start, end] （左包右不包) 中子数组最大值。
如果 start == end，那么 maxSubArraySum 直接返回 nums[start] 就可以了。
连续子序列的最大和主要由这三部分子区间里元素的最大和得到：
- 第 1 部分：子区间
[left, mid]：maxSubArraySum(nums, left, mid) - 第 2 部分：子区间
[mid + 1, right]：maxSubArraySum(nums, mid + 1, right) - 第 3 部分：包含子区间
[mid , mid + 1]的子区间，即nums[mid]与nums[mid + 1]一定会被选取：分别从 mid 左边扩展，和右边扩展，找出两边和最大的时候，然后加起来就可以了。
对它们三者求最大值即可。
- 时间复杂度：
O(nlogn) - 空间复杂度：
O(1)
Java
public class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
return maxSubArraySum(nums, 0, len - 1);
}
private int maxCrossingSum(int[] nums, int left, int mid, int right) {
// 一定会包含 nums[mid] 这个元素
int sum = 0;
int leftSum = Integer.MIN_VALUE;
// 左半边包含 nums[mid] 元素，最多可以到什么地方
// 走到最边界，看看最值是什么
// 计算以 mid 结尾的最大的子数组的和
for (int i = mid; i >= left; i--) {
sum += nums[i];
if (sum > leftSum) {
leftSum = sum;
}
}
sum = 0;
int rightSum = Integer.MIN_VALUE;
// 右半边不包含 nums[mid] 元素，最多可以到什么地方
// 计算以 mid+1 开始的最大的子数组的和
for (int i = mid + 1; i <= right; i++) {
sum += nums[i];
if (sum > rightSum) {
rightSum = sum;
}
}
return leftSum + rightSum;
}
private int maxSubArraySum(int[] nums, int left, int right) {
if (left == right) {
return nums[left];
}
int mid = (left + right) >>> 1;
return max3(maxSubArraySum(nums, left, mid),
maxSubArraySum(nums, mid + 1, right),
maxCrossingSum(nums, left, mid, right));
}
private int max3(int num1, int num2, int num3) {
return Math.max(num1, Math.max(num2, num3));
}
}
Python
from typing import List
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
size = len(nums)
if size == 0:
return 0
return self.__max_sub_array(nums, 0, size - 1)
def __max_sub_array(self, nums, left, right):
if left == right:
return nums[left]
mid = (left + right) >> 1
return max(self.__max_sub_array(nums, left, mid),
self.__max_sub_array(nums, mid + 1, right),
self.__max_cross_array(nums, left, mid, right))
def __max_cross_array(self, nums, left, mid, right):
# 一定包含 nums[mid] 元素的最大连续子数组的和，
# 思路是看看左边"扩散到底"，得到一个最大数，右边"扩散到底"得到一个最大数
# 然后再加上中间数
left_sum_max = 0
start_left = mid - 1
s1 = 0
while start_left >= left:
s1 += nums[start_left]
left_sum_max = max(left_sum_max, s1)
start_left -= 1
right_sum_max = 0
start_right = mid + 1
s2 = 0
while start_right <= right:
s2 += nums[start_right]
right_sum_max = max(right_sum_max, s2)
start_right += 1
return left_sum_max + nums[mid] + right_sum_max