20170706
今天再做這題甥材，寫出來(lái)了拉盾。這題之前說(shuō)的「局部最優(yōu)解」「全局最優(yōu)解」可以這么理解姊途，局部最優(yōu)解就相當(dāng)于dp[i-1]钉疫，因?yàn)槲覍懲陿?biāo)準(zhǔn)dp后很容易發(fā)現(xiàn)這個(gè)dp其實(shí)只需要知道前一位的狀態(tài)硼讽，所以就用個(gè)int來(lái)滾動(dòng)就行了，這個(gè)int就是所謂的局部最優(yōu)解牲阁。然后之前說(shuō)的局部最優(yōu)解必須包含當(dāng)前數(shù)字理郑，其實(shí)就是因?yàn)檫@題要求的是連續(xù)的subarray。
//標(biāo)準(zhǔn)
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;
}
//滾動(dòng)
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題咨油，一月份的時(shí)候做的您炉，現(xiàn)在再做又一時(shí)想不起來(lái)了。役电。這題是DP的思想赚爵，但是有很多種思路；最近看了code ganker的一些題目很多都用到了「局部最優(yōu)解」「全局最優(yōu)解」這個(gè)概念法瑟，比如Jump Game冀膝，Best Time to Buy and Sell Stock等。
這種思想的核心是霎挟，「局部最優(yōu)解」local表示「必須包含當(dāng)前一步操作」時(shí)候的最優(yōu)解窝剖，全局最優(yōu)解global就是代表全局最優(yōu)解，每步比較local和global酥夭。
State transition equation:
dp[i] = dp[i-1] >0 ? dp[i-1] + nums[i] : nums[i]
這題的方程赐纱，要注意是根據(jù)dp[i-1] >0的正負(fù)來(lái)判斷脊奋，跟nums[i]無(wú)關(guān)。
第二點(diǎn)疙描，由于「局部最優(yōu)解」local表示「必須包含當(dāng)前一步操作」時(shí)候的最優(yōu)解诚隙，所以這題dp數(shù)組的最后一位不能代表最優(yōu)結(jié)果，而是要維護(hù)的global起胰。
因?yàn)橹恍枰耙粋€(gè)位置的值久又，所以這道題可以狀態(tài)壓縮，可以這么寫：
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;
}
有時(shí)候我想不通為什么需要比較局部和最優(yōu)效五，原因就是局部因?yàn)橐?dāng)前的值所以有一定局限性地消。比如這道題，如果test case是一串負(fù)數(shù)畏妖，那global的作用就顯而易見了脉执。
我昨天有個(gè)疑問(wèn)，是不是所以DP都需要用到一個(gè)數(shù)組保存狀態(tài)瓜客，空間換時(shí)間嘛适瓦。事實(shí)上不是的竿开，有些題目只需要用到之前一個(gè)子狀態(tài)谱仪，或者可以用空間輪換，就不需要數(shù)組否彩。比如疯攒，利用常規(guī)路子，這題還可以這樣寫：
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;
}
本質(zhì)上列荔，dp[i]就相當(dāng)于local敬尺。
另外這題還有一種divide and conquer做法，挺復(fù)雜的先不討論了贴浙。
