問(wèn)題描述：
給定長(zhǎng)度為n的整數(shù)序列，a[1...n], 求[1,n]某個(gè)子區(qū)間[i , j]使得a[i]+…+a[j]和最大，或者求出最大的這個(gè)和。如果該序列的所有元素都是負(fù)整數(shù)時(shí)定義其最大子段和為0。
例如(-2,11,-4,13,-5,2)的最大子段和為20,所求子區(qū)間為[2,4]。
問(wèn)題分析：
最直接的想法就是利用遍歷法遍歷所有的可能，然后找到最大的那個(gè)，顯然這不是一種有效的方法，但切實(shí)可行。在第二章的時(shí)候?qū)W習(xí)了分治方法，想到也可以把序列拆分成兩部分，答案就在前半段或者后半段或者是穿過(guò)兩段中間的部分。
暴力遍歷法：
就是找到所有可能的結(jié)果然后再判斷找到符合要求的那一個(gè)。首先我們需要一個(gè)循環(huán)來(lái)遍歷從第一個(gè)位置到最后一個(gè)位置：for(int i = 0;i < n; i++)，然后還需要一個(gè)內(nèi)層循環(huán)來(lái)遍歷從當(dāng)前位置到最后一個(gè)位置，來(lái)分別計(jì)算當(dāng)前的最大子段和：
int maxSum(int n, int[] a, int besti, int bestj) {
int sum = 0;
for (int i = 1; i <= n; i++) {
int thissum = 0;
for (int j = i; j <= n; j++) {
thissum += a[j - 1];
if (thissum > sum) {
sum = thissum;
besti = i;
bestj = j;
} // end if
} // end inner for
} // end out for
return sum;
} // end maxSum
很明顯該算法的計(jì)算時(shí)間是O(n2)。
分治法：
針對(duì)最大字段和這個(gè)具體問(wèn)題本身的結(jié)構(gòu)，還可以從算法設(shè)計(jì)的策略上對(duì)上述O(n2)計(jì)算時(shí)間算法加以更深刻的改進(jìn)。
如果將給定的序列a[1..n]分成長(zhǎng)度相等的兩段a[1..n/2]和a[n/2+1:n]，分別求出這兩段的最大字段和。則該給定序列的最大字段和有三種情行：
- ①和a[1..n/2]的最大字段和相同。
- ②和a[n/2+1:n]的最大字段和相同。
- ③最大字段和包含兩部分，一部分在a[1..n/2]中，另一部分在a[n/2+1..n]中。
前兩種情形我們可以用遞歸方法求出，第三種情形可以分別求出兩部分的最大字段和值再相加（注：a[1..n/2]這部分求最大字段和要以a[n/2]結(jié)束，a[n/2+1..n] 這部分求最大字段和要以a[n/2+1]開(kāi)始）。序列的最大字段和即為這三種情形的最大值。
static int maxSubSum(int[] a, int left, int right) {
int sum = 0;
if (left == right) {
sum = a[left - 1] > 0 ? a[left - 1] : 0;
} else {
int center = (left + right) / 2;
int leftSum = maxSubSum(a, left, center);
int rightSum = maxSubSum(a, center + 1, right);
int s1 = 0;
int lefts = 0;
for (int i = center; i >= left; i--) {
lefts += a[i - 1];
if (lefts > s1) s1 = lefts;
}
int s2 = 0;
int rights = 0;
for (int i = center + 1; i <= right; i++) {
rights += a[i - 1];
if (rights > s2) s2 = rights;
}
sum = s1 + s2;
if(sum < leftSum) sum = leftSum;
if(sum < rightSum) sum = rightSum;
} // end if
return sum;
} // end maxSubSum
該算法的計(jì)算時(shí)間為O(nlogn)。
動(dòng)態(tài)規(guī)劃算法：
如果我們定義一個(gè)b[j]表示到當(dāng)前位置為止，最大的字段和，那么事情就會(huì)變得更加簡(jiǎn)單：
static int maxSum(int n, int[] a) {
int sum = 0, b = 0;
for (int i = 1; i <= n; i++) {
if (b > 0) b += a[i - 1];
else b = a[i - 1];
if (b > sum) sum = b;
}
return sum;
}
該算法的計(jì)算時(shí)間需要O(n)。
歡迎轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)注明出處！
簡(jiǎn)書(shū)ID：@我沒(méi)有三顆心臟
github：wmyskxz
歡迎關(guān)注公眾微信號(hào)：wmyskxz_javaweb
分享自己的Java Web學(xué)習(xí)之路以及各種Java學(xué)習(xí)資料
