題目
解析
第一種解法——暴力枚舉法 O(N^3)
從左往右依次找出所有的子序列并計(jì)算其每個(gè)子序列的和，最后返回最大的
//暴力破解O(N^3)
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {// 子序列左端點(diǎn)
for (int j = i; j < nums.length; j++) {// 子序列右端點(diǎn)
int sum = 0;
for (int k = i; k <= j; k++) {//暴力計(jì)算
sum += nums[k];
}
if (max < sum) {
max = sum;
}
}
}
return max;
}
第二種解法——改進(jìn)的暴力枚舉法 O(N^2)
在第一種解法的過程中波桩，事實(shí)上我們是在找到子序列之后再進(jìn)行計(jì)算的建丧，其實(shí)完全可以邊找邊計(jì)算塞俱，這樣就可以減少一層循環(huán)了
//暴力破解改進(jìn)O(N^2)
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {// 子序列左端點(diǎn)
int sum = 0;
for (int j = i; j < nums.length; j++) {// 子序列右端點(diǎn)
sum += nums[j];//這一步相當(dāng)于每次根據(jù)前一次的序列來計(jì)算新的序列和
if (max < sum)
max = sum;
}
}
return max;
}
第三種——掃描法 O(N)
基本思想：當(dāng)我們加上一個(gè)正數(shù)時(shí)贿衍，和會(huì)增加；當(dāng)我們加上一個(gè)負(fù)數(shù)時(shí)澜驮，和會(huì)減少澜术。如果當(dāng)前得到的序列和是一個(gè)負(fù)數(shù)艺蝴，那么下一個(gè)數(shù)無論正負(fù)加上該序列都會(huì)減小，所以這個(gè)序列和應(yīng)當(dāng)在接下來的累加中被拋棄
//掃描法
/**
* curSum 表示當(dāng)前執(zhí)行過程中的和鸟废，
* 如果當(dāng)前序列執(zhí)行過程的和小于0猜敢，說明再往后加只會(huì)減小當(dāng)前序列和，此時(shí)curSum應(yīng)該轉(zhuǎn)變?yōu)閚ums[i],然后開始計(jì)算新的序列和
*/
public int maxSubArray(int[] nums) {
int curSum = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
if (curSum < 0)
curSum = nums[i];
else
curSum += nums[i];
if (curSum > max)
max = curSum;
}
return max;
}
