Kadane's algorithm (Maximum subarray)

Kadane’s algorithm (Maximum subarray)

最近有点时间，抽空刷下leetcode，先从easy的开始刷：）基本都很简单，可是做到了 Maximum subarray 的时候，有点不会了。仔细想想，O(N)的算法貌似有点想不出来，于是看了点资料，理解了好久才想明白了，觉得自己真是笨了。

首先我们来看下题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

下面直接贴自己理解的想法了，具体的算法可以直接看Kadane’s algorithm

首先，我们要解出某个最大和的子串，那么每个子串必定有开始点和结束点吧！那么我们就遍历数组，找出所有结束点之前的最大子串就行了。

不必从0遍历，我们首先定义两个变量，一个变量是总的最大子串和(TotalSum ts)，还有一个是某个索引前最大的子串和(Previous sum ps)，当某个索引的最大子串和大于了总的后，我们将总的进行一下更新。

开始遍历前，我们将ps和ts赋值为索引0的值，然后进行遍历。我们模拟一下遍历的逻辑，前面的序号为遍历的索引，比如1. 则为遍历第一个元素，也就是 input[1] (1)，当前ps=-2，ts=-2。

input[1]=1, ps=-2, ts=-2

我们首先看一下索引1之前的最大的子串和(ps)，为-2，假设我们当前的索引是i，那么ps肯定是包含了i-1的，下面的处理我们会看到原因。因为为负数，那么以索引1为结束点的最大子串应该为多少？当然是抛弃之前的子串和，直接使用索引1的值了。所以我们就知道以下的规律。

当ps[,i-1]为负数的时候，我们不要将input[i]与其相加，直接将input[i]当作结束点为i的最大子串和

当ps[,i-1]为正数的时候，我们相加，之前的最大子串为正数，为什么不加上去变得更大呢？

也就是当我们知道了索引i之前的最大子串和ps[,i-1]的时候，ps[,i]的值只有两种可能，一种就是ps[,i]+input[i]，另一种就是input[i]。

于是根据上面的规则，ps=1。也就是索引1（包括它之前的）的最大子串和为1，1比ts大，则ts也变为了1。

input[2]=-3, ps=1, ts=1

很简单，索引2之前的最大子串为1，正数，我们继续相加

ps=-2 ts=1

input[3]=4, ps=-2, ts=1

索引3之前的最大子串和是负数，为什么要相加呢，直接把索引3的值当做最大子串和

ps=4 ts=4

input[4]=-1, ps=4, ts=4

ps=3 ts=4

input[5]=2, ps=3, ts=4

ps=5 ts=5

input[6]=1, ps=5, ts=5

ps=6 ts=6

input[7]=-5

ps=1 ts=6

input[8]=4

ps=5 ts=6

于是最终的最大子串和为6。

大家可以细想下，怎么得出最大子串的开始和结束索引。

下面贴一个C++的实现：

class MaximumSubarray {
public:
    static int main(vector<int>& nums) {
        // Kadane's algorithm
        // https://en.wikipedia.org/wiki/Maximum_subarray_problem
        if (nums.empty()) {
            return 0;
        }

        // Total max sum is the maximum sum of the nums
        int nTotalMaxSum = nums[0];
        // Previous max sum is the maximum sum before the i
        int nPrevMaxSum = nums[0];

        // Start index of the maximum array
        int nStart = 0;
        // End index of the maximum array
        int nEnd = 0;

        for (int i = 1; i < int(nums.size()); i++) {
            // At the beginning of the loop, we already known the maximum sum of index 0 (just the value of nums[0])
            // and previous maximum sum of index 0. In the loop, we should calculate the maximum sum of index i, there are
            // two scenarios:
            if (nPrevMaxSum > 0) {
                // 1: The previous maximum sum before i is positive, we should always add nums[i] to it (MUST add the nums[i]) and get the sum of i as the
                // maximum previous sum of index i.
                nPrevMaxSum += nums[i];
            } else {
                // 2: The previous maximum sum before i is negative, do not add it
                nPrevMaxSum = nums[i];
                nStart = i;
            }
            if (nPrevMaxSum > nTotalMaxSum) {
                nTotalMaxSum = nPrevMaxSum;
                nEnd = i;
            }
        }

        return nTotalMaxSum;
    }
};

Kadane's algorithm (Maximum subarray)