跳至主要內容

hot150-14-Kadane算法

holic-x...大约 10 分钟算法算法

难度说明：🟢简单🟡中等🔴困难

hot150-14-Kadane算法

​ Kadane's算法是一种用于解决最大子数组和问题（Maximum Subarray Sum Problem）的动态规划算法。该问题的目标是在一个给定数组中找到一个连续子数组，使得子数组的和最大。算法的基本思想是通过迭代数组的每个元素，维护两个变量：当前最大子数组和以及全局最大子数组和。在每一步中，都考虑是否将当前元素添加到当前最大子数组和中，或者重新开始一个新的子数组。这样一步步地迭代数组，最终得到全局最大子数组和

🟡01-最大子数组和（53）

1.题目内容

给你一个整数数组 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

2.题解思路

👻方法1：动态规划

  • 思路分析：中规中矩按照动态规划的解题步骤进行思考

    • 动态规划解析步骤模板：

      • 【步骤1】：确定dp数组及下标含义（根据穷举规律来理解分析）
      • 【步骤2】：得到推导公式（结合规律得到dp[k]的推导公式，即dp[k]与前面的元素有什么联系）
      • 【步骤3】：初始化dp数组（处理初始状态和一些临界的情况）
      • 【步骤4】：确定循环（通过循环和推导公式填充dp数组）
      • 【步骤5】：验证dp数组正确性

    • 最大子数组之和

      • 【1】dp[i]设定表示以i位置元素（nums[i]）结尾的子数组的最大和
      • 【2】推导公式：dp[i]=max{dp[i-1]+nums[i],nums[i]}（思考i和i-1的关系）
        • 已知i-1位置的最大子数组之和，则对于第i个位置而言只需要考虑是否要拼在前一个序列后面
          • 因为此处dp的设定是记录以当前元素结尾的子数组的最大和，因此必须以nums[i]结尾，因此此处是对dp[i-1]的判断，如果它能带来正效益就加入，不能就切断只保留nums[i]，进而达到状态转移方程
      • 【3】基于上述步骤构建dp数组，还需要对这个dp数组中的每个元素进行遍历，进而得到整个数组的最大子数组和
        • 优化：也可以在步骤2推导dp[i]的遍历过程中同步更新这个max（此处为了语义拆分开来）
/**
 * 53 最大子数组和
 */
public class Solution1 {
    /**
     * 动态规划思路：
     * 1.dp[i] 数组表示以i位置结尾的子数组和的最大值（可以通过累加来更新这个值），初始化
     * 2.状态转移方程：dp[i] = max{dp[i-1]+nums[i],nums[i]}
     *  - dp[i]的选择必须以num[i]结尾，因此其只需要考虑dp[i-1]是否可以给它带来正效益，如果不能就直接切断只保留nums[i]
     */
    public int maxSubArray(int[] nums) {
        // 1.定义dp数组
        int[] dp = new int[nums.length];
        dp[0] = nums[0];

        // 2.遍历数组元素，更新值
        for (int i = 1; i < nums.length; i++) {
            // dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            if (dp[i - 1] >= 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = Math.max(dp[i - 1], nums[i]);
            }
        }

        // 3.遍历dp数组，获取到dp数组的最大值
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < dp.length; i++) {
            max = Math.max(max, dp[i]);
        }

        // 返回结果
        return max;
    }
}

  • 复杂度分析

    • 时间复杂度：O（n） n 为数组长度，此处的设定为了区分语义需要遍历两次数组（一次num、一次dp）

    • 空间复杂度：O（n）需要构建dp数组存储以i位置元素结尾的最大子数组和

👻方法2：Kadane算法（动态规划的空间优化版本）

​ 基于动态规划的思路，可以看到dp[i]只关注dp[i-1]和当前的nums[i]，因此此处可以对原有的动态规划版本进行优化：两个变量

  • 【优化1】空间优化：只需要用一个变量pre始终指向以上一个元素结尾的最大子数组和
  • 【优化2】时间优化：对于max的更新也可以同步在循环遍历的过程中进行更新
/**
 * 53 最大子数组和
 */
public class Solution3 {
    /**
     * 动态规划空间优化版本：Kadane算法
     */
    public int maxSubArray(int[] nums) {
        /**
         * 因为dp[i]只和dp[i-1]、nums[i]相关，因此可以只用一个变量始终指向上一个位置的最大连续子数组和，并同步更新max
         */
        int preMax = 0, max = Integer.MIN_VALUE;
        // 遍历元素，更新
        for (int i = 0; i < nums.length; i++) {
            preMax = Math.max(preMax + nums[i], nums[i]); // 累加和
            max = Math.max(preMax, max);
        }
        // 返回结果
        return max;
    }
}

  • 复杂度分析

    • 时间复杂度：O（n）n为数组长度，仅需遍历一次

  • 空间复杂度：O（1）仅用两个变量存储元素（常数级别的消耗）

🟡02-环形最大子数组和（918）

1.题目内容

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

示例 1：

输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3

示例 2：

输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10

示例 3：

输入：nums = [3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

2.题解思路

👻方法1：分段处理

  • 思路分析：分析环形情况下最大子数组和出现的情况

    • 【1】拆解出现最大子数组和的两种场景：中间段（和最大子数组和的思路一致）、头尾段（最大前缀和 + 固定后缀和）
    • 【2】分别计算这两种场景的最大子数组和（max1、max2），取得最大值

  • 场景分析

    • 【场景1】构成最大子数组和的子数组为nums[i,j]（共j-i个元素，元素个数不能超过n）
    • 【场景2】构成最大子数组和的子数组为nums[0,i] + nums[j,n]

image-20241101094838211

​ 上述的第1种情况和【非环形数组求最大子数组和】的情况是一样的，此处继续分析第2种情况：

  • 【场景2】中的情况可以拆分为两部分求解：
    • nums[0,i]是数组的某一前缀，nums[j,n]是数组的某一后缀
    • 遍历时可以通过枚举j进而确定sum(nums[j:n])的值，右边坐标点确定后则可进一步确定[0,j-1]范围内的最大前缀和，然后将两者相加并进行更新
/**
 * 918 环形子数组的最大和（4 ms）
 */
public class Solution3 {
    public int maxSubarraySumCircular(int[] nums) {
        /**
         * 拆分为两部分：
         * [场景1]：中间段
         * - 思路和单数组求解最大子数组和一致
         * [场景2]：头尾段（最大前缀和+固定后缀和）
         * - 1.[0，i] 的最大前缀和
         * - 2.[j,n] 的固定后缀和
         */
        int len = nums.length;

        /**
         * 场景1：求最大子数组和（Kadane 算法优化版本）
         */
        int pre = nums[0]; // pre 指向以上一位置结尾的最大子数组和
        int max1 = nums[0]; // max1 记录数组整体的最大子数组和（遍历的时候同步更新）
        for(int i=1;i<len;i++){
            pre = Math.max(pre+nums[i],nums[i]);
            max1 = Math.max(pre,max1);
        }

        /**
         * 场景2：求头（最大前缀和）+尾（固定后缀和）
         * 前缀累加和：sum[i] = sum[i-1] + nums[i-1] => res = res + nums[i-1]（空间优化）
         */
        int[] leftMax = new int[len]; // leftMax[i] 指向当前位置的最大前缀和
        int curSum = 0; // 当前累加和
        leftMax[0] = 0;
        // 1.计算每个位置的最大前缀和 (从第一个元素遍历)
        for(int i=1;i<len;i++){
            curSum = curSum + nums[i-1];
            leftMax[i] = Math.max(leftMax[i-1],curSum);
        }

        // 2.逆序遍历计算固定后缀和（此处逆序遍历就和上面的正序遍历i保持一致）
        int rightSum = 0;
        int max2 = Integer.MIN_VALUE;
        for(int i=len-1;i>=0;i--){
            rightSum = rightSum + nums[i]; // 固定后缀和
            max2 = Math.max(max2,rightSum+leftMax[i]); // 更新【场景2】中的最大值
        }

        // 最终返回max1、max2两种场景的最大的情况
        return Math.max(max1,max2);
    }
}

优化版本

​ 基于上述分析可以看到，根据解题思路可以得到上述的算法设计，实际上还可以进一步进行时间和空间的优化。例如场景1和场景2（头段部分）实际是对数组元素的一次遍历过程中求的所需值，因此此处可以将这两部分合在一起

  • 最大子数组和（Kadane 算法优化版本）
    • pre、max 实现空间优化
  • 最大前缀和（空间优化）
    • leftMax[i]记录当前位置的最大前缀和
      • 最大前缀和可以通过每次累加后同步更新sum[i] = sum[i-1] + nums[i-1] => res = res + nums[i-1]（空间优化）
/**
 * 918 环形子数组的最大和
 */
public class Solution4 {
    public int maxSubarraySumCircular(int[] nums) {
        /**
         * 拆分为两部分：
         * [场景1]：中间段
         * - 思路和单数组求解最大子数组和一致
         * [场景2]：头尾段（最大前缀和+固定后缀和）
         * - 1.[0，i] 的最大前缀和
         * - 2.[j,n] 的固定后缀和
         */
        int len = nums.length;

        // 场景1：求最大子数组和（Kadane 算法优化版本）所需参数
        int pre = nums[0]; // pre 指向以上一位置结尾的最大子数组和
        int max1 = nums[0]; // max1 记录数组整体的最大子数组和（遍历的时候同步更新）

        // 场景2：求头（最大前缀和）+尾（固定后缀和） 针对头段部分求解所需参数
        int[] leftMax = new int[len]; // leftMax[i] 指向当前位置的最大前缀和
        int curSum = 0; // 当前累加和
        leftMax[0] = 0;

        // 遍历数组元素分别进行求解
        for (int i = 1; i < len; i++) {
            // 求最大子数组和
            pre = Math.max(pre + nums[i], nums[i]);
            max1 = Math.max(pre, max1);
            // 求最大前缀和
            curSum = curSum + nums[i - 1]; // sum[i] = sum[i-1] + nums[i-1] => res = res + nums[i-1]（空间优化）
            leftMax[i] = Math.max(leftMax[i - 1], curSum);
        }

        // 2.逆序遍历计算固定后缀和（此处逆序遍历就和上面的正序遍历i保持一致）
        int rightSum = 0;
        int max2 = Integer.MIN_VALUE; // max2 记录场景2中的最大连续环形子数组和
        for (int i = len - 1; i >= 0; i--) {
            rightSum = rightSum + nums[i]; // 固定后缀和
            max2 = Math.max(max2, rightSum + leftMax[i]); // 更新【场景2】中的最大值
        }

        // 最终返回max1、max2两种场景的最大的情况
        return Math.max(max1, max2);
    }
}
  • 复杂度分析
    • 时间复杂度：O（n）遍历数组元素（遍历两遍数组）
    • 空间复杂度：O（n）需要存储leftMax最大前缀和，且需额外的常数级别空间存储

👻方法2：滑动窗口

​ 思路分析：正常情况下容易联想到通过复制一份数组，然后将环变成单数组的形式来实现（在长度为2n的数组上，寻找长度不超过n的最大子数组和）。然后将题目转化为借助滑动窗口的思路来实现，需注意这个滑动窗口的大小不是固定的，但最大长度不能超过n

0  字
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.1.3
一人の境 Copyright © 2019-未知 holic-x
Copyright © 2025 holic-x