Leetcode Leetcode 53- 最大子段和
1. 题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。1
2
3输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
2. 思路
2.1 分治
这个没啥好说的，经典题，当时在算法书上印象比较深刻的就是用分治：
- 最大子段和在左半部分
- 最大子段和在右半部分
- 最大子段和横跨了左右，包含了mid对应的元素在内。
其中1和2中是会有明显的分治情况出现的，最后三个情况取最大，没什么好说的，时间复杂度为 O(n*logn)，空间复杂度O（1）。
2.2 动态规划
有意思的是，这题的题目上有这么一句话：
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解.
What??? 原来分治不是最优解，居然也能AC。然后看了一下讨论区，我反正是不知道那群人在扯什么玩意儿。。我在百度上看到这么一段解释，清晰明了，上个图：
3. 代码
3.1 分治求解
战胜 30%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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63/**
* @ClassName MaxSubSequence
* @Deacription // TODO
* @Author LiuZhian
* @Date 2019-10-30 18:58
* @Version 1.0
**/
public class MaxSubSequence {
public int maxSubArray(int[] nums) {
// ① 分治法
return maxSub(nums, 0, nums.length - 1);
}
public int maxSub(int[] nums, int left, int right) {
// 思路是：分治求解. 以中间值为界限，可能出现下面3种情况：
// 1. 最大子段和在左边
// 2. 最大子段和在右边
// 3. 最大子段和横跨左右两段，用双指针求解即可
if (left == right) // 分治的边界情况
return nums[left];
int mid = (left + right) / 2;
int left_max = maxSub(nums, left, mid);
int right_max = maxSub(nums, mid + 1, right);
int cross_mid_left = 0; // 横跨中间的左半部分
int left_part_max = nums[mid];
for (int l = mid; l >= left; l--) {
cross_mid_left += nums[l];
if (cross_mid_left > left_part_max)
left_part_max = cross_mid_left;
}
int cross_mid_right = 0; // 横跨中间的左半部分
int right_part_max = nums[mid + 1];
for (int r = mid + 1; r <= right; r++) {
cross_mid_right += nums[r];
if (cross_mid_right > right_part_max)
right_part_max = cross_mid_right;
}
// 整体为左半部分最大+右半部分最大
int cross_mid_max = left_part_max + right_part_max;
// 返回3种情况的最大值
int max = cross_mid_max;
if (left_max > max)
max = left_max;
if (right_max > max)
max = right_max;
return max;
}
public static void main(String[] args) {
int[] nums = {-1};
MaxSubSequence m = new MaxSubSequence();
System.out.println(m.maxSubArray(nums));
}
}
3.2 动态规划
战胜 99.97%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
29
30
31
32
33
34
35
36
37
38/**
* @ClassName MaxSubSequence
* @Deacription // TODO
* @Author LiuZhian
* @Date 2019-10-30 18:58
* @Version 1.0
**/
public class MaxSubSequence {
public int maxSubArray(int[] nums) {
// ② 动态规划
if(nums.length==1)
return nums[0];
int[] c = new int[nums.length];
c[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] + c[i - 1] > nums[i])
c[i] = nums[i] + c[i - 1];
else
c[i] = nums[i];
}
int maxSubSum = c[0];
for (int i = 1; i < nums.length; i++)
if (c[i] > maxSubSum)
maxSubSum = c[i];
return maxSubSum;
}
public static void main(String[] args) {
int[] nums = {-1};
MaxSubSequence m = new MaxSubSequence();
System.out.println(m.maxSubArray(nums));
}
}
