20170706

今天再做这题，写出来了。这题之前说的「局部最优解」「全局最优解」可以这么理解，局部最优解就相当于dp[i-1]，因为我写完标准dp后很容易发现这个dp其实只需要知道前一位的状态，所以就用个int来滚动就行了，这个int就是所谓的局部最优解。然后之前说的局部最优解必须包含当前数字，其实就是因为这题要求的是连续的subarray。

//标准
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
//滚动
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int curMax = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (curMax > 0) {
                curMax = curMax + nums[i];
            } else {
                curMax = nums[i];
            }
            max = Math.max(curMax, max);
        }
        return max;
    }

---

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.

一道easy题，一月份的时候做的，现在再做又一时想不起来了。。这题是DP的思想，但是有很多种思路；最近看了code ganker的一些题目很多都用到了「局部最优解」「全局最优解」这个概念，比如Jump Game，Best Time to Buy and Sell Stock等。

这种思想的核心是，「局部最优解」local表示「必须包含当前一步操作」时候的最优解，全局最优解global就是代表全局最优解，每步比较local和global。

State transition equation:

dp[i] = dp[i-1] >0 ? dp[i-1] + nums[i] : nums[i]

这题的方程，要注意是根据dp[i-1] >0的正负来判断，跟nums[i]无关。
第二点，由于「局部最优解」local表示「必须包含当前一步操作」时候的最优解，所以这题dp数组的最后一位不能代表最优结果，而是要维护的global。

因为只需要前一个位置的值，所以这道题可以状态压缩，可以这么写：

    public int maxSubArray(int[] nums) {
        if (nums.length == 0) return 0;
        int local = nums[0];
        int global = nums[0];
        //local[i] = local[i-1] < 0 ? nums[i]: local[i-1]+nums[i]

        for (int i = 1; i < nums.length; i++) {
            local = local > 0 ? local + nums[i] : nums[i];
            global = Math.max(local, global);
        }
        return global;
    }

有时候我想不通为什么需要比较局部和最优，原因就是局部因为要包含当前的值所以有一定局限性。比如这道题，如果test case是一串负数，那global的作用就显而易见了。

我昨天有个疑问，是不是所以DP都需要用到一个数组保存状态，空间换时间嘛。事实上不是的，有些题目只需要用到之前一个子状态，或者可以用空间轮换，就不需要数组。比如，利用常规路子，这题还可以这样写：

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;
}

本质上，dp[i]就相当于local。

---

另外这题还有一种divide and conquer做法，挺复杂的先不讨论了。