《算法導論》一書中對最大字段和可謂講的是栩栩如生，楚楚動人。如果簡單的說最大字段和，沒有意義。而《算法導論》上舉了一個股票的例子。根據股票每天結束的價格來求出一段時間内何時買入何時賣出能是收益最大。把問題做一個轉換，求出相鄰天數的股票價格的內插補點（周二 - 周一 = 內插補點），然後求出連續天數內插補點和的最大值，即為最大收益，是以就是最大子段和的問題。
還有一點說明的是算法的實作是和語言沒有關系的，下面是用OC來實作的，你也可以用Java, PHP, C++等你拿手的語言進行實作，算法注重的還是思想。
求此問題是通過分治法來做的，通過遞歸方式來進行分治。原問題可以分為三種情況，求原數組中左半的最大字段和，求原數組中右半部最大字段和，求跨越中間位置部分的最大字段和，然後在三個最大字段和中去最大的字段和，即為原問題的解。即為分解，計算，合并的過程。
一、求解跨越中點部分的最大字段和
1.編寫相應的代碼
分析：跨越中點的子數組有一個共同特點, 就是都可以被分為兩部分Array[i] (low <= i <= mid) 和 Array[j](mid < j <= high)兩部分，是以我們求出這兩部分的最大字段和，然後相加，就是我們要求的跨越中點部分的最大字段和。具體代碼如下：
思路分析：
1.先求左邊的最大字段和并記錄對應的起始位置的下标
2.在求右邊的最大字段和，并記錄對應的結束位置的下标
3.把兩個和相加，即為求的解
1 //一次求解跨越中點的最大字段和（跨越中點的最大字段和可以分為Array[i>=low…………mid]和Array[mid+1……j<=high]兩部分，
2 //是以求出兩部分的字段和進行相加，就是跨越中點的最大字段和）
3 +(NSMutableDictionary *) findMaxCrossingSubarrayWithArray: (NSMutableArray *)array
4 WithLow: (NSInteger) low
5 WithMid: (NSInteger) mid
6 WithHigh: (NSInteger) high
7 {
8 //暫存左邊的最大字段和
9 NSInteger leftMaxSum = 0;
10 NSInteger leftTempSum = 0;
11
12 //leftMaxStarIndex預設隻是不再左邊
13 NSInteger leftMaxStarIndex = mid;
14
15 //循環求解左邊含有mid元素的最大字段和
16 for (NSInteger i = mid; i >= low; i --)
17 {
18 leftTempSum += [array[i] intValue];
19
20 //暫存最大字段和
21 if (i == mid || leftTempSum > leftMaxSum) {
22 leftMaxSum = leftTempSum;
23 leftMaxStarIndex = i;
24 }
25
26 }
27
28
29
30
31 //右邊的字段和的計算
32 //暫存左邊的最大字段和
33 NSInteger rightMaxSum = 0;
34 NSInteger rightTempSum = 0;
35
36 NSInteger rightMaxEndIndex = mid;
37
38 //循環求解左邊含有mid元素的最大字段和
39 for (NSInteger i = mid + 1; i <= high; i ++)
40 {
41 rightTempSum += [array[i] intValue];
42
43 //暫存最大字段和
44 if (i == mid+1 || rightTempSum > rightMaxSum) {
45 rightMaxSum = rightTempSum;
46 rightMaxEndIndex = i;
47 }
48 }
49
50
51
52 NSLog(@"leftStarIndex = %ld, rightEndIndex = %ld, subMaxSum = %ld", leftMaxStarIndex, rightMaxEndIndex, leftMaxSum + rightMaxSum);
53 //擷取最大子數組
54 NSRange subRange = NSMakeRange(leftMaxStarIndex, rightMaxEndIndex-leftMaxStarIndex+1);
55
56 NSArray *subArray = [array subarrayWithRange: subRange];
57 NSLog(@"本輪遞歸所得最大子數組如下：");
58 [Sort displayArrayWithArray:(NSMutableArray *)subArray];
59
60
61
62 NSMutableDictionary *resultDic = [NSMutableDictionary dictionaryWithCapacity: 3];
63 [resultDic setObject:@(leftMaxStarIndex) forKey:kLEFTSTARINDEX];
64 [resultDic setObject:@(rightMaxEndIndex) forKey:kRIGHTENDINDEX];
65 [resultDic setObject:@(leftMaxSum + rightMaxSum) forKey:kSUBMAXSUM];
66
67 return resultDic;
68
69 } 2.對上面的方法進行測試，我們還是生成随機的數組，但是數組中要有正數和負數，生成随機數的代碼如下：
1 //生成測試随機數組
2 NSMutableArray *array = [[NSMutableArray alloc] init];
3 UInt count = 10;
4 for (int i = 0; i < count; i ++) {
5 NSInteger tempInteger = arc4random()%100;
6
7 if (tempInteger%2 == 1) {
8 tempInteger = -tempInteger;
9 }
10 NSNumber *temp = @(tempInteger);
11 [array addObject:temp];
12 } 3.進行上面代碼的測試
(1),如果數組中隻有一個數，那個最大字段和就是本身，測試代碼如下：
1 //一次尋找跨過中點的最大字段和
2 [Sort findMaxCrossingSubarrayWithArray:array WithLow:0 WithMid:(NSInteger)(array.count-1)/2 WithHigh:array.count-1]; 運作結果如下：
如果數組中又兩個數那麼就是兩個數的和，運作結果如下：
下面是10個資料運作的結果，最大子數組肯定是包括array[mid]這一項的，因為我們求得就是過中點的最大字段和。
二、遞歸分解問題
下面我們将遞歸把問題分解成更小的問題，對于被程式來說就是把原始數組遞歸分解成單個元素，這樣單個元素的最大字段和就是本身了，然後我在進行子問題的合并，在求解的過程中我們要求出過中點的最大字段和，遞歸函數如下：
1 +(NSMutableDictionary *) findMaxSubArrayWithArray: (NSMutableArray *) array
2 WithLow: (NSInteger) low
3 WithHigh: (NSInteger) high
4 {
5 NSMutableDictionary *resultDic = [[NSMutableDictionary alloc] initWithCapacity:3];
6 //遞歸結束條件:遞歸到隻有一個元素時結束遞歸
7 if (low == high) {
8 resultDic[kLEFTSTARINDEX] = @(low);
9 resultDic[kRIGHTENDINDEX] = @(high);
10 resultDic[kSUBMAXSUM] = array[low];
11
12 return resultDic;
13 }
14
15
16 NSInteger mid = (low + high) / 2;
17 //遞歸左半部分
18 NSMutableDictionary * leftResultDic = [self findMaxSubArrayWithArray:array WithLow:low WithHigh:mid];
19
20 //遞歸右半部分
21 NSMutableDictionary * rightResultDic = [self findMaxSubArrayWithArray:array WithLow:mid + 1 WithHigh:high];
22
23 //計算中間部分
24 NSMutableDictionary * midResultDic = [self findMaxCrossingSubarrayWithArray:array WithLow:low WithMid:mid WithHigh:high];
25
26 //找出三部分中的最大值
27 if([leftResultDic[kSUBMAXSUM] intValue] >= [rightResultDic[kSUBMAXSUM] intValue] && [leftResultDic[kSUBMAXSUM] intValue] >= [midResultDic[kSUBMAXSUM] intValue])
28 {
29 return leftResultDic;
30 }
31
32 if([rightResultDic[kSUBMAXSUM] intValue] >= [leftResultDic[kSUBMAXSUM] intValue] && [rightResultDic[kSUBMAXSUM] intValue] >= [midResultDic[kSUBMAXSUM] intValue])
33 {
34 return rightResultDic;
35 }
36
37
38 return midResultDic;
39 } 先遞歸分解左半部分，求出左半部分的最大字段和，然後再求出右半部分的最大字段和，最後求出過中點的最大字段和，然後合并解，求出三者中最大的，下面的代碼是進行測試調用的代碼：
1 //求最大字段和
2 NSMutableDictionary *dic = [Sort findMaxSubArrayWithArray:array WithLow:0 WithHigh:array.count-1];
3
4 NSLog(@"最終結果如下：================================================");
5
6 NSLog(@"leftStarIndex = %@, rightEndIndex = %@, subMaxSum = %@", dic[kLEFTSTARINDEX], dic[kRIGHTENDINDEX], dic[kSUBMAXSUM]);
7 //擷取最大子數組
8 NSRange subRange = NSMakeRange([dic[kLEFTSTARINDEX] intValue], [dic[kRIGHTENDINDEX] intValue]-[dic[kLEFTSTARINDEX] intValue]+1);
9
10 NSArray *subArray = [array subarrayWithRange: subRange];
11 NSLog(@"最大子數組如下：");
12 [Sort displayArrayWithArray:(NSMutableArray *)subArray]; 下面是具體的運作結果：
三、最後給出暴力求解的代碼如下，上面的時間複雜度是O(nlgn), 而暴力求解為O(n^2),代碼如下：
1 //暴力求最大字段和
2 +(void)findMaxSubSumArrayWithArray: (NSMutableArray *) array{
3
4
5 NSInteger tempSum = 0;
6
7 NSInteger starIndex = 0;
8 NSInteger endIndex = 0;
9
10 for (int i = 0; i < array.count; i ++)
11 {
12 NSInteger sum = 0;
13 for (int j = i; j < array.count; j ++)
14 {
15 sum += [array[j] integerValue];
16
17 if (j == 0 || tempSum <= sum)
18 {
19 tempSum = sum;
20 starIndex = i;
21 endIndex = j;
22 }
23
24 }
25
26 }
27 NSLog(@"\n\n暴力求解的結果如下：");
28 NSLog(@"leftStarIndex = %ld, rightEndIndex = %ld, subMaxSum = %ld", starIndex, endIndex, tempSum);
29 //擷取最大子數組
30 NSRange subRange = NSMakeRange(starIndex, endIndex-starIndex+1);
31
32 NSArray *subArray = [array subarrayWithRange: subRange];
33 NSLog(@"本輪遞歸所得最大子數組如下：");
34 [Sort displayArrayWithArray:(NSMutableArray *)subArray];
35
36 } 運作結果如下（上面是遞歸求解，下面是暴力破解）：
作者：青玉伏案
出處：http://www.cnblogs.com/ludashi/
本文版權歸作者和共部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。
如果文中有什麼錯誤，歡迎指出。以免更多的人被誤導。
收履歷：某網際網路公司，招聘iOS/Android靠譜工程師，入職後，可内部聯系樓主，有小禮品贈送，有意者可郵箱投遞履歷：[email protected]