最大子序和-贪心算法

贪心算法的理论基础

总结：代码随想录

最大子序和

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

例如：对于数组 [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
它能够找出和最大的连续子数组（子数组是数组中的一个连续部分。在这里是 [ 4, -1, 2, 1 ]，其和为 6）
并返回这个最大和的值。
Leetcode题目链接

思路

说实话一开始看到这个题目，脑子的反应就是想用暴力解法，结果一试一试，还真行。哈哈。

思路：暴力解法的思路，第一层 for 就是设置起始位置，第二层 for 循环遍历数组寻找最大值。

代码如下：

class Solution {
public int maxSubArray(int[] nums) {
    int result =Integer.MIN_VALUE;
    int count = 0;
    for (int i = 0; i < nums.length; i++) { // 设置起始位置
        count = 0;
        for (int j = i; j < nums.length; j++) { // 每次从起始位置i开始遍历寻找最大值
            count += nums[j];
            result = count > result ? count : result;
        }
    }
    return result;


}
}

但是时间复杂度：O(n^2)
空间复杂度：O(1)，不推荐，还有更好的算法

那么就是贪心算法(其实也还有其他的解法，例如：dp动态规划)

代码：

class Solution {
public int maxSubArray(int[] nums) {
    if (nums.length == 1){
        return nums[0];
    }
    int sum = Integer.MIN_VALUE; //sum：用于记录在遍历数组过程中找到的最大子数组的和，
    //初始化为 Integer.MIN_VALUE（Java 中 int 类型能表示的最小值），这样可以确保后续在比较和更新最大和时，任何有效的子数组和都能够比初始值大，从而可以正确地更新 sum 的值。
    int count = 0; //count：用于累计当前正在考虑的连续子数组的元素和，初始化为 0，随着遍历数组不断累加元素的值来更新这个累计和
    for (int i = 0; i < nums.length; i++){
        count += nums[i];
        sum = Math.max(sum, count); // 取区间累计的最大值（相当于不断确定最大子序终止位置）
        if (count <= 0){
            count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
        }
    }
   return sum;
}
}