题目地址

https://leetcode.com/problems/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.

思路

C++ 解法一：

``````class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = INT_MIN, curSum = 0;
for (int num : nums) {
curSum = max(curSum + num, num);
res = max(res, curSum);
}
return res;
}
};

``````

Java 解法一：

``````public class Solution {
public int maxSubArray(int[] nums) {
int res = Integer.MIN_VALUE, curSum = 0;
for (int num : nums) {
curSum = Math.max(curSum + num, num);
res = Math.max(res, curSum);
}
return res;
}
}

``````

C++ 解法二：

``````class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.empty()) return 0;
return helper(nums, 0, (int)nums.size() - 1);
}
int helper(vector<int>& nums, int left, int right) {
if (left >= right) return nums[left];
int mid = left + (right - left) / 2;
int lmax = helper(nums, left, mid - 1);
int rmax = helper(nums, mid + 1, right);
int mmax = nums[mid], t = mmax;
for (int i = mid - 1; i >= left; --i) {
t += nums[i];
mmax = max(mmax, t);
}
t = mmax;
for (int i = mid + 1; i <= right; ++i) {
t += nums[i];
mmax = max(mmax, t);
}
return max(mmax, max(lmax, rmax));
}
};

``````

Java 解法二：

``````public class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 0) return 0;
return helper(nums, 0, nums.length - 1);
}
public int helper(int[] nums, int left, int right) {
if (left >= right) return nums[left];
int mid = left + (right - left) / 2;
int lmax = helper(nums, left, mid - 1);
int rmax = helper(nums, mid + 1, right);
int mmax = nums[mid], t = mmax;
for (int i = mid - 1; i >= left; --i) {
t += nums[i];
mmax = Math.max(mmax, t);
}
t = mmax;
for (int i = mid + 1; i <= right; ++i) {
t += nums[i];
mmax = Math.max(mmax, t);
}
return Math.max(mmax, Math.max(lmax, rmax));
}
}
``````

思路 2

复杂度分析

• 时间复杂度： `O(n^3) - n 是数组长度`
• 空间复杂度： `O(1)`

复杂度分析

• 时间复杂度： `O(n^2) - n 是数组长度`
• 空间复杂度： `O(n) - prefixSum 数组空间为n`

复杂度分析

• 时间复杂度： `O(n) - n 是数组长度`
• 空间复杂度： `O(1)`

解法四 - 分治法

`left = nums[0]...nums[m - 1]``right = nums[m + 1]...nums[n-1]`

1. 考虑中间元素`nums[m]`, 跨越左右两部分，这里从中间元素开始，往左求出后缀最大，往右求出前缀最大， 保持连续性。
2. 不考虑中间元素，最大子序列和出现在左半部分，递归求解左边部分最大子序列和
3. 不考虑中间元素，最大子序列和出现在右半部分，递归求解右边部分最大子序列和

复杂度分析

• 时间复杂度： `O(nlogn) - n 是数组长度`
• 空间复杂度： `O(logn)` - 因为调用栈的深度最多是 logn。

解法五 - 动态规划

`dp[i] - 表示到当前位置 i 的最大子序列和`

`dp[i] = max(dp[i - 1] + nums[i], nums[i])`

`currMaxSum - 累计最大和到当前位置i`

`maxSum - 全局最大子序列和`:

• `currMaxSum = max(currMaxSum + nums[i], nums[i])`
• `maxSum = max(currMaxSum, maxSum)`

复杂度分析

• 时间复杂度： `O(n) - n 是数组长度`
• 空间复杂度： `O(1)`

关键点解析

1. 暴力解，列举所有组合子序列首尾位置的组合，求解最大的子序列和， 优化可以预先处理，得到前缀和
2. 分治法，每次从中间位置把数组分为左右中三部分， 分别求出左右中（这里中是包括中间元素的子序列）最大和。对左右分别深度递归，三者中最大值即为当前最大子序列和。
3. 动态规划，找到状态转移方程，求到当前位置最大和。

代码 (`Java/Python3/Javascript`)

解法二 - 前缀和 + 暴力

Java code

``````class MaximumSubarrayPrefixSum {
public int maxSubArray(int[] nums) {
int len = nums.length;
int maxSum = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < len; i++) {
sum = 0;
for (int j = i; j < len; j++) {
sum += nums[j];
maxSum = Math.max(maxSum, sum);
}
}
return maxSum;
}
}
``````

Python3 code `(TLE)`

``````import sys
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
maxSum = -sys.maxsize
sum = 0
for i in range(n):
sum = 0
for j in range(i, n):
sum += nums[j]
maxSum = max(maxSum, sum)

return maxSum
``````

JavaScript code from @lucifer

``````function LSS(list) {
const len = list.length;
let max = -Number.MAX_VALUE;
let sum = 0;
for (let i = 0; i < len; i++) {
sum = 0;
for (let j = i; j < len; j++) {
sum += list[j];
if (sum > max) {
max = sum;
}
}
}

return max;
}
``````

解法三 - 优化前缀和

Java code

``````class MaxSumSubarray {
public int maxSubArray3(int[] nums) {
int maxSum = nums[0];
int sum = 0;
int minSum = 0;
for (int num : nums) {
// prefix Sum
sum += num;
// update maxSum
maxSum = Math.max(maxSum, sum - minSum);
// update minSum
minSum = Math.min(minSum, sum);
}
return maxSum;
}
}
``````

Python3 code

``````class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
maxSum = nums[0]
minSum = sum = 0
for i in range(n):
sum += nums[i]
maxSum = max(maxSum, sum - minSum)
minSum = min(minSum, sum)

return maxSum
``````

JavaScript code from @lucifer

``````function LSS(list) {
const len = list.length;
let max = list[0];
let min = 0;
let sum = 0;
for (let i = 0; i < len; i++) {
sum += list[i];
if (sum - min > max) max = sum - min;
if (sum < min) {
min = sum;
}
}

return max;
}
``````

解法四 - 分治法

Java code

``````class MaximumSubarrayDivideConquer {
public int maxSubArrayDividConquer(int[] nums) {
if (nums == null || nums.length == 0) return 0;
return helper(nums, 0, nums.length - 1);
}
private int helper(int[] nums, int l, int r) {
if (l > r) return Integer.MIN_VALUE;
int mid = (l + r) >>> 1;
int left = helper(nums, l, mid - 1);
int right = helper(nums, mid + 1, r);
int leftMaxSum = 0;
int sum = 0;
// left surfix maxSum start from index mid - 1 to l
for (int i = mid - 1; i >= l; i--) {
sum += nums[i];
leftMaxSum = Math.max(leftMaxSum, sum);
}
int rightMaxSum = 0;
sum = 0;
// right prefix maxSum start from index mid + 1 to r
for (int i = mid + 1; i <= r; i++) {
sum += nums[i];
rightMaxSum = Math.max(sum, rightMaxSum);
}
// max(left, right, crossSum)
return Math.max(leftMaxSum + rightMaxSum + nums[mid], Math.max(left, right));
}
}
``````

Python3 code

``````import sys
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
return self.helper(nums, 0, len(nums) - 1)
def helper(self, nums, l, r):
if l > r:
return -sys.maxsize
mid = (l + r) // 2
left = self.helper(nums, l, mid - 1)
right = self.helper(nums, mid + 1, r)
left_suffix_max_sum = right_prefix_max_sum = 0
sum = 0
for i in reversed(range(l, mid)):
sum += nums[i]
left_suffix_max_sum = max(left_suffix_max_sum, sum)
sum = 0
for i in range(mid + 1, r + 1):
sum += nums[i]
right_prefix_max_sum = max(right_prefix_max_sum, sum)
cross_max_sum = left_suffix_max_sum + right_prefix_max_sum + nums[mid]
return max(cross_max_sum, left, right)
``````

JavaScript code from @lucifer

``````function helper(list, m, n) {
if (m === n) return list[m];
let sum = 0;
let lmax = -Number.MAX_VALUE;
let rmax = -Number.MAX_VALUE;
const mid = ((n - m) >> 1) + m;
const l = helper(list, m, mid);
const r = helper(list, mid + 1, n);
for (let i = mid; i >= m; i--) {
sum += list[i];
if (sum > lmax) lmax = sum;
}

sum = 0;

for (let i = mid + 1; i <= n; i++) {
sum += list[i];
if (sum > rmax) rmax = sum;
}

return Math.max(l, r, lmax + rmax);
}

function LSS(list) {
return helper(list, 0, list.length - 1);
}
``````

解法五 - 动态规划

Java code

``````class MaximumSubarrayDP {
public int maxSubArray(int[] nums) {
int currMaxSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < nums.length; i++) {
currMaxSum = Math.max(currMaxSum + nums[i], nums[i]);
maxSum = Math.max(maxSum, currMaxSum);
}
return maxSum;
}
}
``````

Python3 code

``````class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
max_sum_ending_curr_index = max_sum = nums[0]
for i in range(1, n):
max_sum_ending_curr_index = max(max_sum_ending_curr_index + nums[i], nums[i])
max_sum = max(max_sum_ending_curr_index, max_sum)

return max_sum
``````

JavaScript code from @lucifer

``````function LSS(list) {
const len = list.length;
let max = list[0];
for (let i = 1; i < len; i++) {
list[i] = Math.max(0, list[i - 1]) + list[i];
if (list[i] > max) max = list[i];
}

return max;
}
``````

扩展

• 如果数组是二维数组，求最大子数组的和？
• 如果要求最大子序列的乘积？

评论
0 评论