卡丹算法

Kadane 算法

​ Kadane 算法是一种用于解决最大子数组和问题的高效算法。它的核心思想是动态规划，通过在遍历数组的过程中实时计算子数组的和，从而找到最大的子数组和。

求最大和的题目：

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

代码：

class Solution {
    public int maxSubArray(int[] nums) {
        // 将 max 和 currentSum 初始化为数组的第一个元素
        int max = nums[0];
        int currentSum = nums[0];
        
         // 从第二个元素开始遍历数组
        for(int i = 1; i < nums.length; i++) {
            // 更新 currentSum 为当前元素或 currentSum + 当前元素的较大值
            currentSum = Math.max(nums[i], currentSum + nums[i]);
             // 更新 max，如果 currentSum 大于 max
            max = Math.max(currentSum, max);
        }
        return max;
    }
}

算法步骤：

1、初始化：

• 定义两个变量：
  • max：用于存储当前找到的最大子数组和，初始值设置为数组的第一个元素。
  • currentSum：用于存储当前子数组的和，初始值也设置为数组的第一个元素。

2、遍历数组：

• 从数组的第二个元素开始遍历，依次考虑每个元素。
• 对于每个元素 nums[i]，更新 currentSum：
  • currentSum = max(nums[i], currentSum + nums[i])
  • 这一步的意思是，决定是将当前元素 nums[i] 包含在现有的子数组中（即 currentSum + nums[i]），还是以当前元素为新子数组的起点（即 nums[i]）。
• 更新 max：
  • max = max(max, currentSum)
  • 如果当前的 currentSum 大于 max，则更新 max。

3、返回结果：

• 遍历结束后，max 就是所求的最大子数组和。

时间复杂度和空间复杂度：

​ Kadane 算法的时间复杂度为 O(n)，因为它只需要遍历一次数组。空间复杂度为 O(1)，因为只使用了常数额外空间。

实际示例：

假设有一个数组 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]，我们来看看 Kadane 算法的运行过程：

• 初始化：max = -2, currentSum = -2
• 遍历：
  • i = 1: currentSum = max(1, -2 + 1) = 1, max = max(-2, 1) = 1
  • i = 2: currentSum = max(-3, 1 - 3) = -2, max = max(1, -2) = 1
  • i = 3: currentSum = max(4, -2 + 4) = 4, max = max(1, 4) = 4
  • i = 4: currentSum = max(-1, 4 - 1) = 3, max = max(4, 3) = 4
  • i = 5: currentSum = max(2, 3 + 2) = 5, max = max(4, 5) = 5
  • i = 6: currentSum = max(1, 5 + 1) = 6, max = max(5, 6) = 6
  • i = 7: currentSum = max(-5, 6 - 5) = 1, max = max(6, 1) = 6
  • i = 8: currentSum = max(4, 1 + 4) = 5, max = max(6, 5) = 6

最终，max 的值为 6，即最大子数组和为 6（子数组为 [4, -1, 2, 1]）。

求最大积的题目：

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

代码：

class Solution {
    public int maxProduct(int[] nums) {
        // 初始化最大乘积、最小乘积和全局最大乘积
        int maxEndingHere = nums[0];
        int minEndingHere = nums[0];
        int maxproduct = nums[0];
        
         // 从第二个元素开始遍历
        for(int i = 1; i < nums.length; i++) {
            int current = nums[i];
            
            // 如果当前元素是负数，交换最大和最小乘积
            if(current < 0) {
                int temp = minEndingHere;
                minEndingHere = maxEndingHere;
                maxEndingHere = temp;
            }
            
            // 计算新的最大和最小乘积
            maxEndingHere = Math.max(current, maxEndingHere * current);
            minEndingHere = Math.min(current, minEndingHere * current);
            
            // 更新全局最大乘积
            maxproduct = Math.max(maxEndingHere, maxproduct);
        }
        return maxproduct;
    }
}

代码解释

1. 初始化：
   • maxEndingHere 和 minEndingHere 初始化为数组的第一个元素。
   • maxProduct 初始化为第一个元素，作为全局最大乘积。
2. 遍历数组：
   • 从第二个元素开始遍历。
   • 如果当前元素为负数，交换 maxEndingHere 和 minEndingHere，因为负数的乘法会改变符号。
   • 更新 maxEndingHere 为当前元素与之前的最大乘积的乘积，或者当前元素本身。
   • 更新 minEndingHere 为当前元素与之前的最小乘积的乘积，或者当前元素本身。
   • 更新 maxProduct 为当前的 maxEndingHere 和之前的最大值的较大值。
3. 遇到负数时交换最大乘积和最小乘积，因为最小乘积乘一个负数会大于最大乘积乘一个负数

实际示例：

假设输入为 nums = [2, 3, -2, 4]，执行流程如下：

1. 初始化：
   • maxEndingHere = 2, minEndingHere = 2, maxProduct = 2
2. 遍历：
   • i = 1（current = 3）：
     • 更新：maxEndingHere = max(3, 3 * 2) = 6
     • 更新：minEndingHere = min(3, 3 * 2) = 3
     • 更新：maxProduct = max(2, 6) = 6
   • i = 2（current = -2）：
     • 交换：maxEndingHere = 3, minEndingHere = 6
     • 更新：maxEndingHere = max(-2, -2 * 3) = -2
     • 更新：minEndingHere = min(-2, -2 * 6) = -12
     • 更新：maxProduct = max(6, -2) = 6
   • i = 3（current = 4）：
     • 更新：maxEndingHere = max(4, 4 * -2) = 4
     • 更新：minEndingHere = min(4, 4 * -12) = -48
     • 更新：maxProduct = max(6, 4) = 6

最终，返回的 maxProduct 为 6。