简介Kadane算法及相关的普通动态规划

简介Kadane算法及相关的普通动态规划

本文详细论述Kadane算法的经典题目，并通过“首先列出动态规划解法，再改为Kadane算法解法”的方式，讲解二者的不同。最后给出一道Kadane算法变体的题目，解法极为简洁优美。

Kadane算法也是一种动态规划算法，它的时间复杂度也是O(n), 但它与普通的动态规划有什么不同呢？这里先给出结论，不同就是：它的空间复杂度是O(1)，而普通动态规划的空间复杂度是O(n).

下面的例题-1是一道经典的可以用Kadane算法求解的题目。

例题-1 LeetCode-53

给定一个整数数组，求它的子数组之和的最大值。
比如，数组为[-2,1,-3,4,-1,2,1,-5,4], 则子数组元素之和最大为6，因为当子数组为 [4,-1,2,1]时可取得最大值。

解法-1. 普通动态规划法

众所周知，动态规划法需要有一个递推公式。这个公式的思考与解析如下。
假设有一个同样大小的dp数组，其第i个位置的元素dp[i]的含义是：原整数数组s从0至i处且包含元素i时的所有子数组中子数组元素之和的最大值。
听见来很拗口是不是。说白了就是，对于所有的以s[i]为最右元素的子数组求子数组元素之和，最大的那个值就是dp[i].
想一想，如果我们知道了所有的dp[0], dp[1], …,dp[size-1], 那么我们是不是就知道了子数组之和的最大值了呢。
这里要注意的是，当 i < j < size 时， dp[i] 有可能大于 dp[j].
知道 dp[i] 的定义后，那么 dp[i+1] 是什么呢？
很明显，dp[i] 与 dp[i+1] 的差异就在于原数组的第 i+1 个元素，即 s[i+1].
一种可能是：s[i+1]可以被继续累加到当前最大值上，即dp[i]和s[i+1]都是非负数，那么 dp[i+1] = dp[i] + s[i+1]
另一种可能是：s[i+1]不可以被继续累加到当前最大值上， 比如：dp[i]是负数，而s[i+1]又比dp[i]大, 于是只好从s[i+1]开始算，即 dp[i+1] = s[i+1]
综合这2个式子：dp[i+1] = max(dp[i]+s[i+1], s[i+1])
换一种写法： dp[i] = max(dp[i-1]+s[i], s[i])
在当前定义下，我们最后需要返回 dp 数组中的最大元素。

这里有一个问题，为什么不能把 dp[i] 定义为“从0至i处的所有子数组中子数组元素之和的最大值”呢？
如果可以这么定义的话，那么我们就不需要在dp数组中找一个最大值，而只要返回dp数组的最后一个元素即可了。
其实对于有些问题时完全可以这么做的，比如下面的例题-2.
但是对于例题-1来说，鉴于其所求是子数组元素之和的最大值，它相当于对之前的多个元素有依赖关系，如果那样定义的话，则无法建立dp[i+1]和dp[i]之间的递推关系。
这个问题是一个隐藏较深且不太容易解释的问题。喜欢对算法作深入思考的朋友可以多想想这里，看是否有更加简洁精辟的见解。

普通动态规划法的代码还是比较简洁的，如下：

class Solution {
    public int maxSubArray(int[] nums) {
        int [] dp = new int [nums.length];
        dp[0] = nums[0];
        int result = nums[0];
        for (int i=1; i<nums.length; i++) {
            dp[i] = Math.max(nums[i], nums[i]+dp[i-1]);
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}

解法-2. Kadane算法

上面的整个dp数组是否必要呢？
其实不是必要的。公式中的 dp[i] 和 dp[i-1] 看似不同，但其实可以巧妙地用一个变量来代表，从而整个dp数组也就不需要了 – 只用一个变量来维护dp[i]. 所以Kadane算法的空间复杂度是O(1). 这个技巧还是很值得学习的。

代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
        int max_here = nums[0];
        int result = nums[0];
        for (int i=1; i<nums.length; i++) {
            max_here = Math.max(nums[i], nums[i]+max_here);
            result = Math.max(result, max_here);
        }
        return result;
    }
}

例题-1中对于dp[i]的定义还是不那么符合人的直觉的，而下面例题-2对 dp[i] 的设定则非常直接了。

例题-2. LeetCode-121

给定一个整数数组，其中每一个数字代表了股票在当天的价格。你每天只能操作一次，这一次是买或者卖股票，请最大化利润。
比如：[7,1,5,3,6,4]，最大化利润是5. 因为在价格为1的那天买，在价格为6的那天卖，可以得到5的利润。

解法-1. 普通动态规划法

有了前面那么难的题，这题就简单了。对于动态规划，就是主要要考虑递推公式。
设定一个同样大小的数组dp，那么很自然地就想到 dp[i] 就代表到当天为止的最大利润。
那么dp[i+1]是什么呢？ 假设原数组叫prices, 此时相当于多了一个 prices[i+1], 所引起的变化就是也许 prices[i+1] 能得到更高利润。
怎么会得到更高利润呢？如果用prices[i+1]减去之前的最小值，则是它得到的利润值；如果这个值比dp[i]大，则有了更高利润。
由此可见，要记录一个历史最小值。这个并不难实现。
这样一分析，递推公式就出来了： dp[i+1] = max(dp[i], prices[i+1]-minValue)
由此也可见，我们最后需要返回的就是 dp[size-1]，即dp数组的最后一个元素。

普通动态规划法代码如下：

int maxProfit(vector<int>& prices) {
    if (prices.empty()) return 0;

    vector<int> dp(prices.size());
    dp[0] = 0;
    int minPrice = prices[0];

    for (int i=1; i<prices.size(); i++) {
        dp[i] = max(dp[i-1], prices[i] - minPrice);
        if (prices[i] < minPrice) minPrice = prices[i];
    }
    return dp[prices.size()-1];
}

解法-2. Kadane算法

仍然对普通动态规划法稍作优化，用一个变量代替dp[i]和dp[i+1], 由此消除dp数组。
代码如下：

int maxProfit(vector<int>& prices) {
    if (prices.empty()) return 0;

    int max_here = 0;
    int minPrice = prices[0];

    for (int i=1; i<prices.size(); i++) {
        max_here = max(max_here, prices[i] - minPrice);
        if (prices[i] < minPrice) minPrice = prices[i];
    }
    return max_here;
}

除了上面2道例题，有的时候会出现 Kadane 算法的变体。这个时候需要因为一些特殊条件而做出一些巧妙的变化，则可以继续使用Kadane算法。

例题-3 LeetCode-152

给定一个整数数组，求其子数组的乘积最大值。
比如：[2,3,-2,4]，其子数组乘积最大值为6，因为 2x3=6.

首先，还是要找出递推数组。假设dp[i]为“至位置i处的包含了位置i的子数组乘积最大值”，那么对于例子中给定的数组，对应的dp数组是这样的：[2, 6, -2, 4]
所以， dp[i+1] = max(dp[i]*s[i+1], s[i])
由此似乎可以写出程序了。和例题-1很像嘛！是不是直接套就可以了？
但注意这样的数组： [-2, 3, -4], 很明显答案是24，但应用上面算法的dp数组是 [-2, 3, 3].
原因很简单，每遇到负数一次则结果反转，也就是说，如果应用了上面的算法，则-2无法被后面再一次遇到负数时用上。
换句话说，尽管dp[1]为3是正确的，但dp[2]还是3就不正确了，而此时dp[0]或原数组nums[0]的信息无法被dp[2]用上。
至此，普通的动态规划似乎不再能够应用了，因为递推关系似乎无法推出来。怎么办呢？其实Kadane算法仍可以应用。
鉴于负数每乘一次都会反转结果，我们就只好一直乘，直至结尾。如果负数的个数是偶数，则这就是结果（先不考虑0）。
但如果负数的个数是奇数，比如1个，那我们就不知道是在这个负数的左边还是右边会出现乘积最大值了。
这又怎么办呢？也很好办。从左往右和从右往左分别扫一遍。因为我们不可能在一遇到负数的时候就重启计算。
最后，一旦遇到0怎么办呢？这就要重启计算了。相当于数字0将数组分段了。一旦遇到0，则从0后面的第1个数字开始，重启我们的乘法运算，直至下一个0或数组在当前方向上结束。
啰里吧嗦说了很多，但代码其实还是很简洁的。

class Solution {
    public int maxProduct(int[] nums) {
        long r1 = Integer.MIN_VALUE;
        long p1 = 1;
        for (int i=0; i<nums.length; i++) {
            p1 = p1 * nums[i];
            if (p1 > r1) r1 = p1;
            if (p1 == 0) p1 = 1;
        }
        
        long r2 = Integer.MIN_VALUE;
        long p2 = 1;
        for (int i=nums.length-1; i>=0; i--) {
            p2 = p2 * nums[i];
            if (p2 > r2) r2 = p2;
            if (p2 == 0) p2 = 1;
        }

        return (int)(r1>r2?r1:r2);
    }
}

由本题可见，Kadane算法其实可能比普通动态规划更加灵活。

(END)