Home > Archives > 理解Kadane算法

理解Kadane算法

Publish:

最近刷leetcode时遇到一道题:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

做题时想了想,除了暴搜之外没有想到其他的办法,然后看Discuss区,发现一个很有意思的算法:

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

看了很久都没有看明白,去了解了一下历史,发现这是一个著名的求解最大子数组的线性O(n)算法–Kadane算法。

算法的篇幅虽然比较短,但是理解起来比较困难,所以我记录一下我理解的思路,以期帮助有困惑的学习者,也便于复习。

为了更方便的说明这个算法,我先用测试用例进行一次遍历:

测试用例遍历

可以看到的是maxForNow总是存储目前最大的子数组,maxPostfix总是存储最大后缀的子数组。

于是就可以很清晰的理解Kadane算法了:

该算法的本质就是利用动态规划的思想,通过寻找局部最优解 + 状态转移来寻找全局最优解。

用直白的语言说就是:如果我已经知道nums[0]-nums[i - 1]的最大子数组,那么我如何寻找nums[0]-nums[i]的最大子数组。

显然的,nums[0]-nums[i]的最大子数组可能取以下两个值:

1、之前nums[0]-nums[i - 1]时的最大子数组,即之前的maxForNow
2、nums[k]-nums[i](0 <= k <= i),加上nums[i]之后的,由nums[i]及其之前的多个元素构成的最大子数组,也就是最大后缀,我们称之为maxPostfix

于是就很容易理解:

maxForNow = Math.max(maxForNow, maxPostfix);

那么maxPostfix怎么求呢?

同样很显然的,maxPostfix只有可能取以下两个值:

1、previous maxPostfix + nums[i]
2、nums[i]

于是这一语句也容易理解了:

maxPostfix = Math.max(maxPostfix + nums[i], nums[i]);

从nums[0]开始,遍历数组,不断更新maxForNow和maxPostfix,遍历整个数组后,得到maxForNow,就是我们需要的最大子数组。

声明: 本文采用 BY-NC-SA 授权。转载请注明转自: 理解Kadane算法 - 无火的余灰