MaximumSubarray [source code]

public class MaximumSubarray {
static
/******************************************************************************/
public class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) return 0;
        int max_ending_here = 0, max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            max_ending_here += nums[i];
            if (max_ending_here > max) max = max_ending_here;
            if (max_ending_here < 0) max_ending_here = 0;
        }
        return max;
    }
}
/******************************************************************************/

    static public int test(int[] nums) {
        if (nums.length == 0) return 0;
        int max_ending_here = 0, max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            max_ending_here = Math.max(0, max_ending_here + nums[i]);
            if (max_ending_here > max) max = max_ending_here;
        }
        return max;
    }

    //standard Kadane's algorithm
    static int maxSubArraySum(int[] a) {
        int size = a.length;
        int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;

        for (int i = 0; i < size; i++) {
            max_ending_here = max_ending_here + a[i];
            if (max_so_far < max_ending_here)
                max_so_far = max_ending_here;
            if (max_ending_here < 0)
                max_ending_here = 0;
        }
        return max_so_far;
    }

    public static void main(String[] args) {
        MaximumSubarray.Solution tester = new MaximumSubarray.Solution();
        int[] input1 = {-2,1,-3,4,-1,2,1,-5,4};//6
        assert tester.maxSubArray(input1) == 6;
        int[] input2 = {-2, 1};//1
        assert tester.maxSubArray(input2) == 1;
        int[] input3 = {-1};//-1
        assert tester.maxSubArray(input3) == -1;
        System.out.println(tester.maxSubArray(input3));
        System.out.println(maxSubArraySum(input3));
        // System.out.println(test(input3));
    }
}

题目本身并不陌生, 但是没想到虽然感觉自己对Kadane's Algorithm 已经很熟悉, 但是实际上真正自己写的时候才发现, 很多小细节我完全没有掌握; 这种看来的算法, 包括看别人的代码, 看书, 看来的算法, 如果不自己闭卷写一遍, 始终都不是自己的;

首先是两个 max 的 init, 一开始我是把两个都 init 到nums0, 这个也是以前积累的一个经验, 认为这样的 init 是没有问题的; 但是实际上这题这样的做法就正好出问题了;
稍微分析了一下, 这题这里这种 init 方式出问题是有两个原因:

1. max_ending_here这个的下限是0 by definition, 如果你 init 到nums[0], 那么有可能就违背了这个规定;
2. max 这样 init 其实是没问题的, 我试了一下;

究其原因还是max_ending_here这个并不是一个普通的max over the array, 这么简单, 而是一个有特定含义的 max, 所以 init 的时候有自己的方式的要求;

另外一个问题是, 两个 max, 更新顺序是什么?
一开始我是这么写的

max_ending_here = Math.max(0, max_ending_here + nums[i]);  
if (max_ending_here > max) max = max_ending_here;

但是这样写就不对了; 加完了nums[i]之后, 必须先给Max_sofar 一个更新的机会之后, 才决定是否应该将Max_ending_here 归零; 这个写法大部分时间都是没有问题的, 但是我们最后返回的是 max, 如果整个 nums 就只有一个element, 那么你直接max_ending_here在给 max 更新之前就被归零了, 那么 max 能够获得的最小值就是0, max will never be below 0 again other than the initialization to MIN_VALUE. 这个显然是有问题的, 有时候 max 是应该是负值的;

这个算法严格来说其实也是一个标准的历史信息算法: 走到一个 element, 我们做两件事情:

1. 用endinghere 来更新 sofar, 这个是一个读取历史信息的问题;
2. 维护历史信息, 也就是让历史信息反映出我当前这个 element 给历史信息带来的变化; 具体到这个问题来说, 就是如果 endinghere 是负值, 那么我们应该 restart;

这个思路对写一般性的历史信息的 body 内部的顺序有所指导意义: 应该先read/update, 然后 maintain;
这样的一个顺序模板, 可以避免错误;

最后的速度是16(53), 这个题目太老了, 题号是53, 所以最优解太多了;

倒是找到一个比这个速度快的:

public class Solution {  
    public int maxSubArray(int[] nums) {  
        int maxSum = Integer.MIN_VALUE, sum = 0;  

        for(int i = 0; i < nums.length; i++) {  
            if(sum < 0) sum = nums[i];  
            else sum += nums[i];  

            if(sum > maxSum) maxSum = sum;  
        }          
        return maxSum;  
    }  
}

这个其实思路是类似的, 只不过他这里是先 maintain, 然后 read/update. 这个思路我当时有稍微想到了一点;

原来两个都 init到[0]是可以的, 这个是 discussion 上看到的:

public static int maxSubArray(int[] A) {  
    int maxSoFar=A[0], maxEndingHere=A[0];  
    for (int i=1;i<A.length;++i){  
        maxEndingHere= Math.max(maxEndingHere+A[i],A[i]);  
        maxSoFar=Math.max(maxSoFar, maxEndingHere);   
    }  
    return maxSoFar;  
}

只不过 endinghere 的更新方式要稍微改变一下了; 而且这个也是一个先 maintain, 然后read/update的思路;
这个是对应的介绍:
this problem was discussed by Jon Bentley (Sep. 1984 Vol. 27 No. 9 Communications of the ACM P885)
the paragraph below was copied from his paper (with a little modifications)
algorithm that operates on arrays: it starts at the left end (element A[1]) and scans through to the right end (element A[n]), keeping track of the maximum sum subvector seen so far. The maximum is initially A[0]. Suppose we've solved the problem for A[1 .. i - 1]; how can we extend that to A[1 .. i]? The maximum
sum in the first I elements is either the maximum sum in the first i - 1 elements (which we'll call MaxSoFar), or it is that of a subvector that ends in position i (which we'll call MaxEndingHere).
MaxEndingHere is either A[i] plus the previous MaxEndingHere, or just A[i], whichever is larger.

下面是 discussion上面对于这个 followup 的介绍:
Analysis of this problem:
Apparently, this is a optimization problem, which can be usually solved by DP. So when it comes to DP, the first thing for us to figure out is the format of the sub problem(or the state of each sub problem). The format of the sub problem can be helpful when we are trying to come up with the recursive relation.

At first, I think the sub problem should look like: maxSubArray(int A[], int i, int j), which means the maxSubArray for A[i: j]. In this way, our goal is to figure out what maxSubArray(A, 0, A.length - 1) is. However, if we define the format of the sub problem in this way, it's hard to find the connection from the sub problem to the original problem(at least for me). In other words, I can't find a way to divided the original problem into the sub problems and use the solutions of the sub problems to somehow create the solution of the original one.

So I change the format of the sub problem into something like: maxSubArray(int A[], int i), which means the maxSubArray for A[0:i ] which must has A[i] as the end element. Note that now the sub problem's format is less flexible and less powerful than the previous one because there's a limitation that A[i] should be contained in that sequence and we have to keep track of each solution of the sub problem to update the global optimal value. However, now the connect between the sub problem & the original one becomes clearer:

maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0 + A[i];
And here's the code

public int maxSubArray(int[] A) {  
        int n = A.length;  
        int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];  
        dp[0] = A[0];  
        int max = dp[0];  

        for(int i = 1; i < n; i++){  
            dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);  
            max = Math.max(max, dp[i]);  
        }  

        return max;  
}

这个 followup 我自己并没有去想, 不过大概思路我是有的, 就是additional constraint to add DP property to the recursive return value, 同时加上之前的include root in the recursive return value的技巧, 这个我不是第一次碰到了. 他这里大概的意思也是这样,不过没有我想的这么 highlevel; 不过尽管如此, 他的解释还是很有帮助的;

这个题目就比较像前面的diameter 之类的题目, recursion 给一个 value, 然后自己用另外一个方法(这里是遍历找 max, 虽然是融合到1pass 里面去了)来通过这个recursive return value来获得想要的 value. 这个套路见过的确实很多次了, 广泛适用于 recursion/DP/tree 类型的题目;

Problem Description

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.

click to show more practice.

More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Difficulty:Easy
Category:Algorithms
Acceptance:39.43%
Contributor: LeetCode
Companies
linkedin bloomberg microsoft
Related Topics
array dynamic programming divide and conquer
Similar Questions
Best Time to Buy and Sell Stock Maximum Product Subarray