Problem Description
这题有好多种AC的方法。这里我写了两种。
dp[i]表示从0~i之间最大的subarray, 用一个local的数组，来记录局部最优。
那么dp[i] = max{dp[i-1], local[i]}
其中local[i] = max{local[i - 1] + nums[i], nums[i]}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public int (int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int[] dp = new int[nums.length];
int[] local = new int[nums.length];
dp[0] = nums[0];
local[0] = nums[0];
for (int i = 1; i < nums.length; ++i) {
local[i] = Math.max(local[i - 1] + nums[i], nums[i]);
dp[i] = Math.max(dp[i - 1], local[i]);
}
return dp[nums.length - 1];
}
|
感觉这种方法不能算DP，算贪心吧。用一个local数组，来记录，包含i的区间中最优的解。然后再用一个变量来记录最大的局部最优解，最后返回这个变量。
1
2
3
4
5
6
7
8
9
10
11
12
|
public int (int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int[] local = new int[nums.length];
int ans = nums[0];
local[0] = nums[0];
for (int i = 1; i < nums.length; ++i) {
local[i] = Math.max(local[i - 1] + nums[i], nums[i]);
ans = Math.max(ans, local[i]);
}
return ans;
}
|
近期评论