LeetCode 53. Maximum Subarray [Easy]

发表于 更新于 分类于 ， 阅读次数：

题目来源：53. Maximum Subarray - LeetCode

题目难度：Easy

题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

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

解答1[Java]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length <= 0)
            return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];

        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
            max = Math.max(max, dp[i]);
            max = dp[i] > max ? dp[i] : max;
        }
        return max;
    }
}

思路

动态规划。dp[i] 中存储的是 i 之前的最大的子序列和。

时间复杂度 $O(n)$，空间复杂度为 $O(n)$。

解答2[Java]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int curSum = 0;

        for (int n : nums) {
            curSum += n;
            if (curSum > maxSum) {
                maxSum = curSum;
            }
            if (curSum < 0) {
                curSum = 0;
            }
        }

        return maxSum;
    }
}

思路

一直加，用 curSum 表示截至目前的最大正子序和。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。