关于Kadane算法

”最大子数列和问题“应该是最近两年大家面试经常碰到的一道题目了，刷过题的朋友应该也知道这是用Kadane算法解的。我在面试Meta的时候就碰到了Kadane的题，在去年一年的求职过程到最后上岸大厂的过程中，Kadane算是我思考得比较深入的算法之一。

Kadane算法算是动态规划的一个分支，关于动态规划大家应该都很熟悉：它将复杂的问题分解为一组更简单的子问题，每个子问题只解决一次，然后使用基于内存的数据结构(数组、映射等)存储它们的解决方案。因此，下次出现相同的子问题时，只需查找之前计算过的解，而不用重新计算它的解，从而节省了计算时间。

那么Kadane的最经典的案例就是上文提到的“最大子数列和问题”：给定一个整数数组，任务是找出所有非空子数组可能的最大子数组和。设给定数列为A，长度为n。如果用暴力法，那我们就从A[0]遍历到A[n-1]，再从A[1]遍历到A[n]-1...结果时间复杂度为O(n**2)，这显然是不实际的。

所以，我们改用动态规划的思想。而Kadane算法是基础动态规划的优化，用一个指针i保存子数列，用max_sub_sum变量保存我们当前求得的最大子数列解，因此，我们可以写出引用了Kadane的基础子数列解：


代码如下：

1. class Solution(object):
   
2.          def maxSubArrayKadane(self, nums):
   
3.                length = len(nums)
   
4.                 max_ending_here = max_sub_sum = nums[0]
   
5.                 for i in range(1,length):
   
6.                          max_ending_here = max(max_ending_here+nums[i],nums[i])
   
7.                          max_sub_sum = max(max_ending_here, max_sub_sum)
   
8.                 return max_sub_sum</div>

复制代码

其中max_ending_here就是子问题的解：我们把目标数列缩短为以A结尾的子数列，先用子数列，然后将i向后移动，渐渐得目标的解，也就是max_sub_sum。这就是最基础的Kadane算法。

我再分享一个比较让我印象深刻的Follow up：
Best time to sell and buy stock with cold down
股票系列的问题相信大家都很熟悉，算是动态规划的经典了。最简单的股票问题没有cold down，也可以用上述动态规划的思想解决，即找到min(price)和max(profit)即可，但是，一旦加上了cold down，我们要考虑的问题就变多了。

我们依然可以使用Kdane算法的思想解答， 但这次，我们要把子问题的进度分为不同的”状态“。


Held: 持有之前购买的股票。
Sold: 刚刚卖出了一只股票，当前没有持有股票。
Reset: 把这个状态作为起点，此时没有持有股票，之前也没有卖出过股票。更重要的是，它也是Held和Sold之前的短暂状态。由于冷却规则，在售出状态后，不能立即购买，而是被迫进入复位状态。
在我们遍历price数组时，这三种状态的转换规则如下：
Sold转换为Reset,
Reset转换为Held, 或保持Reset
Held转换为Sold，或保持Held。
也就是说:
Sold[i]=hold[i-1]+price[i]
Reset[i]=max(reset[i-1],sold[i-1])
Held[i]=max(Held[i-1],reset[i-1]-price[i])

因此，这次我们在套用kadane算法时，用max找到子问题的解时，要在这三种状态中互相转换，参考代码如下：

1. class Solution(object):
   
2.     def maxProfit(self, prices):
   
3. 
   
4.         sold, held, reset = float('-inf'), float('-inf'), 0
   
5.         for price in prices:
   
6.             # Alternative: the calculation is done in parallel.
   
7.             # Therefore no need to keep temporary variables
   
8.             #sold, held, reset = held + price, max(held, reset-price), max(reset, sold)
   
9.             pre_sold = sold
   
10.             sold = held + price
    
11.             held = max(held, reset - price)
    
12.             reset = max(reset, pre_sold)
    
13.         return max(sold, reset)</div>

复制代码

[/i][/i][/i][/i][/i]

补充内容 (2022-08-28 00:45 +8:00):
求大米求大米