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做法，挺复杂的先不讨论了。
