Kadane 算法

Kadane 算法（Kadane's algorithm）是一种用于解决最大子数组问题的动态规划算法。最大子数组问题的目标是在一个整数数组中找到一个连续的子数组，使得该子数组的和最大。

Kadane 算法的思路很简单：从头到尾遍历数组，用两个变量 max_so_far 和 max_ending_here 分别记录全局最大子数组的和以及当前最大子数组的和，每次遍历更新这两个变量即可。

以下是一些使用Kadane算法解决的LeetCode问题：

• Maximum Subarray（最大子数组和）：leetcode.com/problems/ma…

• Maximum Product Subarray（最大子数组乘积）：leetcode.com/problems/ma…

• Maximum Sum Circular Subarray（环形子数组的最大和）：leetcode.com/problems/ma…

• Partition Array Into Three Parts With Equal Sum（将数组分成和相等的三个部分）：leetcode.com/problems/pa…

• ...

具体实现如下：

1. 将 max_so_far 和 max_ending_here 初始化为第一个元素。

2. 从第二个元素开始遍历数组，对于每个元素执行以下操作：

   • 将 max_ending_here 更新为 max(当前元素, 当前元素 + max_ending_here)，即选择保留当前元素还是加上之前的最大子数组和。
   • 将 max_so_far 更新为 max(max_so_far, max_ending_here)，即更新全局最大子数组和。

3. 返回 max_so_far。

Kadane 算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

---

53. 最大子数组和

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

 

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

 

进阶： 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

普通DP

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0]*len(nums)
        dp[0] = nums[0]
        for i in range(1,len(nums)):
            dp[i] = max(dp[i-1]+nums[i],nums[i])
        return max(dp)

这段代码使用的是动态规划算法。

• 算法维护一个长度为len(nums)的一维数组dp，其中dp[i]表示以位置i为结尾的最大子数组和。初始化dp[0]为nums[0]，因为以位置0结尾的最大子数组就是nums[0]本身。

• 在遍历过程中，对于位置i，可以分两种情况考虑：

  • 一种是将当前位置加入到前面的最大子数组中，

  • 另一种是以当前位置为起点开始新的最大子数组。

  因此，状态转移方程为dp[i] = max(dp[i-1]+nums[i], nums[i])。

• 最后，算法返回dp中的最大值即可。

由于算法只遍历一遍数组，因此时间复杂度为O(n)，其中n为nums的长度。但是由于需要维护一个长度为len(nums)的数组，因此空间复杂度为O(n)。

Kadane 算法

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSoFar = maxEndingHere = nums[0]
        for i in range(1,len(nums)):
            maxEndingHere =  max(maxEndingHere + nums[i],nums[i])
            maxSoFar = max(maxEndingHere, maxSoFar)
        return maxSoFar

这段代码实现了 Kadane 算法来求解最大子数组和。

• 算法维护两个变量，maxSoFar 表示到当前位置为止，已经遍历过的子数组中的最大值，maxEndingHere 表示到当前位置为止，包括当前位置在内的子数组中的最大值。

• 在遍历过程中，对于位置i，可以分两种情况考虑：

  • 一种是将当前位置加入到前面的最大子数组中，

  • 另一种是以当前位置为起点开始新的最大子数组。

  因此，状态转移方程为maxEndingHere = max(maxEndingHere + nums[i],nums[i])。同时，需要更新maxSoFar，以保证到最后返回的是整个数组中的最大子数组和。

• 最后，算法返回maxSoFar即可。

由于算法只遍历一遍数组，因此时间复杂度为O(n)，其中n为nums的长度。同时，由于算法只维护了两个变量，因此空间复杂度为O(1)。

918. 环形子数组的最大和

给定一个长度为 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

 

提示：

• n == nums.length
• 1 <= n <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104

解法思路看这里：✅ [C++]Easy solution with explaination in O(N) time complexity✅

我简单说两句：

1. 最大子数组 不成环 --> 和上一题一样

2. 最大子数组 成环 --> 看下图，总和减去不成环的子数组最小和(total - minSum) === 成环区域的最大和

   

注意：如果数组都是非正数，最小和=整个数组的和，此时total-minSum = 0，这时候最大和就要去1.里边找。

说再多都没用，我们直接上代码就理解了。

DP

先看一个比较直观好理解的代码版本：

这个可以AC，不是最终答案啊！！！

class Solution:
    def maxSubarraySumCircular(self, nums):
        total = sum(nums)
        maxSum = [nums[0]] * len(nums)
        minSum = [nums[0]] * len(nums)
        cirSum = [total - nums[0]] * len(nums)
        for i in range(1, len(nums)):
            maxSum[i] = max(maxSum[i - 1] + nums[i], nums[i])
            minSum[i] = min(minSum[i - 1] + nums[i], nums[i])
            cirSum[i] = total - minSum[i]
        return max(maxSum + cirSum) if cirSum[-1] != 0 else max(maxSum)

调试一下：

• 我们可以看到动态规划过程中的最大子数组和 和 最小子数组和 以及 成环区域最大子数组和。此时整个题目的最大子数组和 就是 从 不成环和成环区域的最大子数组和里边找。

  

• 当全是负数的时候，最后最小子数组和就是整个数组的和，此时成环区域的最大子数组和为0，此时要去不成环区域找。

Kadane

class Solution:
    def maxSubarraySumCircular(self, nums):
        total = sum(nums)
        minEndingHere = minSoFar = maxSoFar = maxEndingHere = nums[0]
        for i in range(1, len(nums)):
            maxEndingHere = max(maxEndingHere + nums[i], nums[i])
            minEndingHere = min(minEndingHere + nums[i], nums[i])
            maxSoFar = max(maxSoFar,maxEndingHere)
            minSoFar = min(minSoFar,minEndingHere)
        return max(maxSoFar,total - minSoFar) if total - minSoFar else maxSoFar

1. 计算数组的总和 total。

2. 初始化 minEndingHere，minSoFar，maxSoFar，maxEndingHere，并将其设置为第一个元素 nums[0]。

3. 循环遍历数组中的每个元素 nums[i]，从第二个元素开始：

   • 计算以当前元素结尾的子数组的最大和 maxEndingHere，使用 Kadane's algorithm。

   • 计算以当前元素结尾的子数组的最小和 minEndingHere，同样使用 Kadane's algorithm。

   • 更新全局最大和 maxSoFar 和全局最小和 minSoFar。

4. 如果数组所有元素都是负数，则返回 maxSoFar。

5. 否则，返回 max(maxSoFar,total - minSoFar)，其中 total - minSoFar 表示跨越数组末尾和数组开头的子数组的最大和。

该算法的时间复杂度为 O(n)O(n)O(n)，其中 nnn 是输入数组 nums 的长度。这是因为算法只需一次遍历输入数组 nums，并且每个元素只被访问一次。在循环遍历中，每次迭代需要常量时间，因此总时间复杂度为 O(n)O(n)O(n)。

该算法的空间复杂度为 O(1)O(1)O(1)，因为它只使用了常数级别的额外空间。算法使用了一些变量来存储中间结果和状态，但它们的数量是固定的，与输入数组 nums 的大小无关。

需要注意的是，由于算法使用了 Kadane's algorithm，它假定输入数组中至少有一个正数元素。否则，最大和将始终为负数，导致算法返回错误的结果。因此，如果输入数组中没有正数元素，则应该特殊处理此情况，例如返回数组中的最大值（即所有元素中的最大负数）。

152. 乘积最大子数组

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

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

 

示例 1:

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

示例 2:

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

 

提示:

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

DP

class Solution:
    def maxProduct(self, nums: [int]) -> int:
        '''
        普通DP：
        维护两个dp数组，因为如果出现负数，会让当前最大值变为最小值，让当前最小值变为最大值
        maxDp[i] = max(maxDp[i-1],maxDp[i-1]*nums[i])
        '''
        maxDp = [nums[0]] * len(nums)
        minDp = [nums[0]] * len(nums)
        for i in range(1, len(nums)):
            maxDp[i] = max(nums[i], maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i])
            minDp[i] = min(nums[i], minDp[i - 1] * nums[i], maxDp[i - 1] * nums[i])
        return max(maxDp)

该函数使用了动态规划的思想，具体实现如下：

1. 定义两个长度与输入数组相同的数组 maxDp 和 minDp，其中 maxDp[i] 表示以第 i 个元素结尾的子数组的最大乘积，minDp[i] 表示以第 i 个元素结尾的子数组的最小乘积（注意这里是最小乘积，因为负数的存在会使得最小值变为最大值）。

2. 初始化 maxDp 和 minDp 的第一个元素为 nums[0]。

3. 遍历数组 nums，从第二个元素开始。对于每个元素 nums[i]，更新 maxDp[i] 和 minDp[i]：

   • maxDp[i] 的值可能是 nums[i]，表示当前元素自成一个子数组。还可能是 maxDp[i - 1] * nums[i]，表示当前元素与前一个元素组成的子数组的最大乘积再乘以当前元素（因为这里要求的是连续子数组）。还可能是 minDp[i - 1] * nums[i]，表示当前元素与前一个元素组成的子数组的最小乘积再乘以当前元素（因为当前元素可能是负数，会让最小乘积变为最大乘积）。
   • minDp[i] 的值的求法与 maxDp[i] 类似，只是把 max 换成了 min，把 min 换成了 max。

4. 返回 maxDp 中的最大值，即为所求的最大乘积。

代码维护了两个数组 maxDp 和 minDp，分别记录以当前位置为结尾的子数组的最大乘积和最小乘积。对于每个位置 i，都需要计算 maxDp[i] 和 minDp[i]，复杂度为 O(n)。最后需要遍历一次 maxDp 数组来找到最大值，复杂度也是 O(n)。因此，总的时间复杂度为 O(n^2)，空间复杂度为 O(n)。

Kadane

class Solution:
    def maxProduct(self, nums: [int]) -> int:
        maxSoFar = nums[0]
        maxEndingHere = nums[0]
        minEndingHere = nums[0]
        for i in range(1, len(nums)):
            maxEndingHere,minEndingHere = max(nums[i],
                                              maxEndingHere * nums[i],
                                              minEndingHere * nums[i]),\
                                          min(nums[i],
                                              minEndingHere * nums[i],
                                              maxEndingHere * nums[i])
            maxSoFar = max(maxSoFar,maxEndingHere)
        return maxSoFar

1. 定义三个变量 maxSoFar、maxEndingHere 和 minEndingHere，其中 maxSoFar 表示到当前位置为止的最大乘积，maxEndingHere 表示以当前位置结尾的子数组的最大乘积，minEndingHere 表示以当前位置结尾的子数组的最小乘积。

2. 初始化 maxSoFar、maxEndingHere 和 minEndingHere 的值都为 nums[0]。

3. 遍历数组 nums，从第二个元素开始。对于每个元素 nums[i]，更新 maxEndingHere 和 minEndingHere：

   • maxEndingHere 的值可能是 nums[i]，表示当前元素自成一个子数组。还可能是 maxEndingHere * nums[i]，表示将当前元素加入之前的子数组（因为这里要求的是连续子数组），这样可以得到一个更大的子数组。还可能是 minEndingHere * nums[i]，表示当前元素加入之前的子数组会让最小乘积变成最大乘积。
   • minEndingHere 的值的求法与 maxEndingHere 类似，只是把 max 换成了 min，把 min 换成了 max。

4. 每次更新 maxEndingHere 后，用其与 maxSoFar 比较，如果 maxEndingHere 更大，就更新 maxSoFar。

5. 返回 maxSoFar，即为所求的最大乘积。

需要维护三个变量 maxSoFar、maxEndingHere 和 minEndingHere，对于每个位置 i，只需要更新 maxEndingHere 和 minEndingHere，然后用 maxEndingHere 更新 maxSoFar。因此，时间复杂度为 O(n)，空间复杂度为 O(1)。