/*     * 53.Maximum Subarray      * 2016-5-7 by Mingyang      * 如果我们从头遍历这个数组。对于数组中的其中一个元素，它只有两个选择： 1.     * 要么加入之前的数组加和之中（跟别人一组）      * 2. 要么自己单立一个数组（自己单开一组）     * 所以对于这个元素应该如何选择，就看他能对哪个组的贡献大。如果跟别人一组     * 能让总加和变大，还是跟别人一组好了；如果自己起个头一组，自己的值比之前加和的值还要大，那么还是自己单开一组好了。     * 所以利用一个dp数组，记录每一轮sum的最大值，dp[i]表示当前这个元素是跟之前数组加和一组还是自己单立一组好，然后维护一个全局最大值即位答案     * 那么这道题目开始想能不能用maxSubArray(int A[], int i, int j), which means the maxSubArray for A[i: j].     * 但是这么写子函数就很难找到这种关系。那么我们接下来就怎么做呢？     * maxSubArray(int A[], int i), which means the maxSubArray for A[0:i ] which must has A[i] as the end element.     * 那么就下来的关系就是：     * dp[i] = Math.max(A[i], dp[i - 1] + A[i]);     * 也就是说对于A[i]到底加不加进来，我们只需要看这个加进来大还是单独大。     * 因为你如果加进来都比单独大，那么后面还是一个增量。     * 千万不要写成：dp[i] = Math.max(dp[i-1], dp[i - 1] + A[i]);      * Kadan's algorithm  O(n) time and O(1) space      */    public static int maxSubArray(int[] A) {        int[] dp = new int[A.length];        int max = A[0];        dp[0] = A[0];        for (int i = 1; i < A.length; i++) {            dp[i] = Math.max(A[i], dp[i - 1] + A[i]);      // 这里只比较了自己另外开一个，和原来的加一起开的区别            max = Math.max(max, dp[i]);        }     //不是每一个dp都是返回最后一个dp值哦！有可能返回全局变量        return max;    }    /*     * 下面是我自己的解法，开始想的有点复杂，然后后面仔细列举一下也是蛮简单的，这里用了一个dp数组     * dp[i]表示包括i在内的连续数组的最大值，而不是到i最优的结果     * [-1,-2]那么dp[1]=-3,因为要把-2包括进来     * 那么如果每个数自己就很大，比加起前面累积的dp还大，那么久自成一家     * 否则的话需要加起来，每次更新dp的时候与全局变量max比较一下     */    public int maxSubArray1(int[] nums) {        int len=nums.length;        int max=nums[0];        int[] dp=new int[len];        dp[0]=nums[0];        for(int i=1;i
     
      nums[i]+dp[i-1]){                dp[i]=nums[i];                max=Math.max(max,dp[i]);            }else{                dp[i]=dp[i-1]+nums[i];                max=Math.max(max,dp[i]);            }        }        return max;    }