###53. Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
第一眼看是一个简单的动态规划问题
dp[i][j] 保存数组从i到j的和，利用下面的dp式进行简化计算
dp[i][j] = dp[i][j-1] + nums[j]
注意要问清楚，当数组为空的时候的返回值是多少
于是写出了如下动态规划代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[][] dp = new int[n][n];
int current_max = Integer.MIN_VALUE;
for (int i=0;i<n;i++){
dp[i][i] = nums[i];
if(dp[i][i] > current_max){
current_max = dp[i][i];
}
for(int j=0; j<=i; j++){
if(i>=1){
dp[j][i] = dp[j][i-1] + nums[i];
if(dp[j][i] > current_max){
current_max = dp[j][i];
}
}
}
}
return current_max;
}
}
|
时间复杂度为$O(n^2)$,提交显示超时。
其实可以优化成$O(n)$
dp[i]表示以i结尾的子串中，最大的数值和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
int current_max = Integer.MIN_VALUE;
if(n == 0){
return current_max;
}
dp[0] = nums[0];
current_max = dp[0];
for(int i=1; i<n; i++){
dp[i] = nums[i] + Math.max(dp[i-1], 0);
current_max = Math.max(current_max, dp[i]);
}
return current_max;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
maxSum = nums[0]
cur = 0
for i in nums:
cur = max(cur+i, i)
maxSum = max(cur, maxSum)
return maxSum
|
