[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.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Constraints:

1 <= nums.length <= 105
-104 <= nums[i] <= 104

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.

最大子数组。

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

思路是动态规划。设 dp[i] 是以 nums[i] 结尾的子数组的和。扫描数组，当遇到某个数 nums[i] 的时候，需要判断 dp[i - 1] 是否小于 0。如果小于 0，nums[i] + dp[i - 1] 的结果只会拖累 dp[i]；如果大于 0，可以将 dp[i] = dp[i - 1] + nums[i] 。最后返回过程中找到的最大的 dp[i] 即可。

时间O(n)

空间O(n)

JavaScript实现

 1 /**
 2  * @param {number[]} nums
 3  * @return {number}
 4  */
 5 var maxSubArray = function(nums) {
 6     let dp = new Array(nums.length);
 7     dp[0] = nums[0];
 8     let res = nums[0];
 9     for (let i = 1; i < nums.length; i++) {
10         dp[i] = dp[i - 1] < 0 ? nums[i] : dp[i - 1] + nums[i];
11         res = Math.max(res, dp[i]);
12     }
13     return res;
14 };

Java实现

 1 class Solution {
 2     public int maxSubArray(int[] nums) {
 3         int[] dp = new int[nums.length];
 4         dp[0] = nums[0];
 5         int res = nums[0];
 6         for (int i = 1; i < nums.length; i++) {
 7             dp[i] = nums[i] + (dp[i - 1] < 0 ? 0 : dp[i - 1]);
 8             res = Math.max(res, dp[i]);
 9         }
10         return res;
11     }
12 }

这种 DP 的思路也有节省空间的做法，其实我们并不一定需要知道每个 dp[i] 值的大小，我们只需要在遍历过程中记录一下最大的 dp 值即可。思路也是很类似，如果之前的值 prev 小于 0，一定会拖累 cur 的，所以 cur = nums[i]；反之如果 prev 大于 0，cur就变为 nums[i] + prev。每次用 res 记录一下当前的子数组的最大值之后，就可以把 cur 赋给 prev 以达到节省空间的目的了。

时间O(n)

空间O(1)

 1 class Solution {
 2     public int maxSubArray(int[] nums) {
 3         int prev = nums[0];
 4         int cur = nums[0];
 5         int res = nums[0];
 6         for (int i = 1; i < nums.length; i++) {
 7             if (prev < 0) {
 8                 cur = nums[i];
 9             } else {
10                 cur = prev + nums[i];
11             }
12             res = Math.max(res, cur);
13             prev = cur;
14         }
15         return res;
16     }
17 }

还有另外一种思路，类似 DP 的做法，是去求局部最大和整体最大。设两个变量 sum 和 res，sum 记录当遍历到 nums[i] 的时候，sum + nums[i] 是否对值的扩大有帮助；res 记录最大的 sum 值。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int maxSubArray(int[] nums) {
 3         int res = nums[0];
 4         int sum = nums[0];
 5         for (int i = 1; i < nums.length; i++) {
 6             sum = Math.max(nums[i], sum + nums[i]);
 7             res = Math.max(res, sum);
 8         }
 9         return res;
10     }
11 }

JavaScript实现

 1 /**
 2  * @param {number[]} nums
 3  * @return {number}
 4  */
 5 var maxSubArray = function(nums) {
 6     let res = nums[0];
 7     let sum = nums[0];
 8     for (let i = 1; i < nums.length; i++) {
 9         sum = Math.max(nums[i], sum + nums[i]);
10         res = Math.max(res, sum);
11     }
12     return res;
13 };