LeetCode_95_MaximumSubarray


1. question: 最大子数组和(简单)

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/maximum-subarray

示例 1:

1
2
3
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

示例 2:

1
2
输入:nums = [1]
输出:1

示例 3:

1
2
输入:nums = [5,4,-1,7,8]
输出:23

提示:

1
2
1 <= nums.length <= 105
-104 <= nums[i] <= 104

2. answers

这道题也是比较经典,其实感觉和贪心并不是很有直接关系,但是也涉及到贪心的思想了。这道题是子数组,即是连续元素和。首先想到的是暴力法,确定子数组的起始和结束位置,遍历求和。毫无疑问超时了。代码如下所示:

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
public class Solution_0095 {

public int maxSubArray(int[] nums) {

// 因为结果是int,所以保证了最坏情况下也在区间内。
int max = Integer.MIN_VALUE;

for (int start = 0; start < nums.length; start++) {

int sum = 0;
for (int end = start; end < nums.length; end++) {

sum += nums[end];
max = Math.max(max, sum);
}
}

return max;
}

public static void main(String[] args) {

// int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int[] nums = {5, 4, -1, 7, 8};

Solution_0095 s = new Solution_0095();

System.out.println(s.maxSubArray(nums));
}
}

超时,就意味着多了很多无用次比较。因此,尝试改进。起始元素如果是负数,那么就没必要开始累加了,进行下个子数组即可。因为是负数,显然负数只会使得最终结果更小。代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int maxSubArray(int[] nums) {

// 因为结果是int,所以保证了最坏情况下也在区间内。
int max = Integer.MIN_VALUE;

for (int start = 0; start < nums.length; start++) {

if(nums[start] <= 0) continue;
int sum = 0;
for (int end = start; end < nums.length; end++) {

sum += nums[end];
max = Math.max(max, sum);
}
}

if(max == Integer.MIN_VALUE){
Arrays.sort(nums);
max = nums[nums.length - 1];
}

return max;
}

但是这样做仍然超时,即还有很多无用次比较。显然,第一个子数组如果是4个元素,那么第二个子数组的前三位元素其实就不需要累加了,也不需要比较了。即相邻子数组之间的重复的部分有很多重复操作。

参考题解的做法:

只要是负数,其实就没必要向后续传递了,即此时累加应该终止,即当前子数组结束。因为负数只会使得结果变得更小。所以,遍历数组,累加,取最大值。如果累加和为负数,那么更新累加值为0,即不再像后续传递。(注意,一定要先累加,再取最大值,这样才能保证是和子数组比较;否则可能会和更新后的0比较。

代码如下所示:

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
public class Solution_0095_03 {

public int maxSubArray(int[] nums) {

// 初始化最大值 为 某个最小的数。
int max = Integer.MIN_VALUE;

// 初始化子数组累加和为0
int sums = 0;

for (int num : nums) {

// 先累加,判断此时的最大值。
sums += num;
max = Math.max(max, sums);

// 如果加上当前数为正数,那么就有可能是最大的;所以子数组无需重新计算。
// 如果是当前子数组累加数为负数,那么就会影响后面的结果。所以子数组需要重新开始。
// 注意,这里设置0,表明不会影响每个元素值。
if (sums <= 0) {
sums = 0;
}
}

return max;
}

public static void main(String[] args) {
System.out.println();

Solution_0095_03 s = new Solution_0095_03();

int[] nums = {-5, -3, -9, -6, -1};
System.out.println(s.maxSubArray(nums));
}
}

3. 备注

参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)代码随想录 (programmercarl.com)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录