最大子序和
题目
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
1
2
3
| 输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
|
递归解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| private static int res;
public static int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
res = nums[0];
maxSum(nums, nums.length - 1);
return res;
}
public static int maxSum(int[] nums, int i) {
if (i == 0) {
return nums[0];
}
int preMax = maxSum(nums, i - 1);
int curMax = preMax > 0 ? preMax + nums[i] : nums[i];
res = Math.max(res, curMax);
return curMax;
}
|
递归加记忆解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| private static int res2;
private static int[] maxEnds;
public static int maxSubArray2(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
maxEnds = new int[nums.length];
Arrays.fill(maxEnds, Integer.MIN_VALUE);
res2 = nums[0];
maxSum2(nums, nums.length - 1);
return res2;
}
public static int maxSum2(int[] nums, int i) {
if (i == 0) {
return nums[0];
}
if (maxEnds[i] != Integer.MIN_VALUE) {
return maxEnds[i];
}
int preMax = maxSum2(nums, i - 1);
int curMax = preMax > 0 ? preMax + nums[i] : nums[i];
res2 = Math.max(res2, curMax);
return curMax;
}
|
动态规划解法
1
2
3
4
5
6
7
8
9
10
11
12
13
| public static int maxSubArray3(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = dp[i - 1] > 0 ? dp[i - 1] + nums[i] : nums[i];
max = Math.max(max, dp[i]);
}
return max;
}
|
滚动优化解法
1
2
3
4
5
6
7
8
9
10
11
12
| public static int maxSubArray4(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int preMax = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
preMax = preMax > 0 ? preMax + nums[i] : nums[i];
max = Math.max(max, preMax);
}
return max;
}
|
关注【憨才好运】微信公众号，了解更多精彩内容⬇️⬇️⬇️
