Kadane‘s Algorithm

Posted on

介绍

计算机历史上有一个非常经典的问题叫做Maximum-Subarray-Problem， 求数组的最大子序列，要求该子序列和为最大值，子序列应当连续。

比如 [−2, 1, −3, 4, −1, 2, 1, −5, 4]， 最大应该子序列为 [4, −1, 2, 1]。

暴力的解法是算出所有的子序列，然后求和，该方法的时间复杂度为O(n^2).

Kadane’s Algorithm

Kadane’s Algorithm是求解该类问题的一个通法，原理是利用Dynamic Programming保存所有以i结尾的子序列的最大长度，dp公式为:

如果以i - 1为结尾的子序列最大值为负，那么不管怎么样，dp[i]就应该从头开始计数，因为前面的子序列已经不再有影响了(dp[i - 1] + nums[i]必然小于nums[i])

Leetcode里有两道经典的题目，用到了这个算法，分别为Leetcode53和Leetcode1186，Leetcode 53是这一算法的直接运用，代码如下：

1
2
3
4
5
6
7
8
9
10
public int maxSubArray(int[] nums) {
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int res = dp[0];
    for(int i = 1; i < nums.length; i++){
        dp[i] = Math.max(dp[i - 1], 0) + nums[i];
        res = Math.max(dp[i], res);
    }
    return res;  
}

Leetcode1186是一个变式，基本思路不变，不过我们可以选择是否删除删除一个元素，显然，如果遇到负数，我们可以考虑将其删除，然后计算两头，对于第i个数字，如果它是负数，则计算以i - 1为结尾的最大子序列和以i + 1为开头的最大子序列，我们分别用dp1，dp2存储这两种状态，原理依旧是Kadane’s Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int maximumSum(int[] arr) {
    int[] dp1 = new int[arr.length];
    int[] dp2 = new int[arr.length];
    dp1[0] = arr[0];
    int res = arr[0];
    for(int i = 1; i < arr.length; i++){
        dp1[i] = Math.max(dp1[i - 1], 0) + arr[i];
        res = Math.max(res,dp1[i]);
    }
    dp2[arr.length - 1] = arr[arr.length - 1];
    for(int i = arr.length - 2; i > -1; --i){
        dp2[i] = Math.max(dp2[i + 1], 0) + arr[i];
    }
    
    for(int i = 1; i < arr.length - 1; i++){
        if(arr[i] < 0)
            res = Math.max(dp1[i - 1] + dp2[i + 1], res);
    }

    return res;
}

总结

为什么突然写这个？ 因为做到1186卡了挺久，当然也有读错题的缘故，不过归根结底还是因为没有对这个方法进行总结，像这种以人名命名的算法还是应当总结下的 :P