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:
示例 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 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 = {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 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;
int sums = 0;
for (int num : nums) {
sums += num; max = Math.max(max, sums);
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)。