贪心算法

题目

给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例1

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

示例2

  • 输入：nums = [1]
  • 输出：1

示例3
输入：nums = [5,4,-1,7,8]
输出：23

《代码随想录》算法公开课
力扣题目链接

思路

暴力解法

  • 暴力解法的思路，第一层for就是设置起始位置，第二层 for循环遍历数组寻找最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution{
    public int maxSubArray(int[] nums){
        //先将结果设为最小整数，以便于后续结果做对比不被影响
        int res = Integer.MIN_VALUE;
        //单个子序列的总和
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            //每次进行新一轮遍历时，都重置子序列和
            count = 0;
            for(int j = i; j < nums,length; j++){
                //固定外层nums[i]移动j指针，寻找最大子序列和
                count += nums[j];
                //当前子序列和大于res时，将其count值赋给res
                res = count > res ? count : res;
            }
        }
        return res;
    }
}

注：此方法的时间复杂度为O(n^2)，空间复杂度为O(1)，一般会超过题目给定的时间限制，提示超时错误

贪心算法

所谓贪心算法，就是在子序和为负数时，直接舍弃当前count，对其count进行重新赋值0的操作，因为负数只会拉低综合，这便是局部最优。

从代码角度上来讲：遍历nums，从头开始用count累积，如果count一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积count了，因为已经变为负数的count，只会拖累总和。

  • 注：这相当于是暴力解法中的不断调整最大子序和区间的起始位置。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxSubArray(int[] nums) {
        //当长度为1时直接返回其值便是最大子序和
        if (nums.length == 1){
            return nums[0];
        }
        //将返回值初始为整型最小值，以便后续赋值
        int max = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; i++){
            count += nums[i];
            //先对比取出最大值，再判断count是否<0，这么做是为了防止最大值便是负数导致遗漏
            max = Math.max(max, count); 
            // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
            if (count <= 0){
                count = 0; 
            }
        }
       return max;
    }
}