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)$。