最近在看算法導(dǎo)論，看到計(jì)算最大子數(shù)組問題顽聂，于是寫了一個(gè)iOS版本的肥惭。

1. 利用分治策略，逐層尋找
2. 最大子數(shù)組存在三種情況：若將數(shù)組在中間元素位置劃分為兩部分芜飘，則最大子數(shù)組可能在中間元素的左半部分务豺、右半部分或者是跨越中間元素的部分。
3. 現(xiàn)在我們將問題一分為三嗦明，在左半部分尋找最大子數(shù)組笼沥，在右半部分尋找最大子數(shù)組，以及在橫跨中間的最大子數(shù)組中尋找三者之中最大的娶牌。而左右兩半部分的情況其實(shí)是以上情況的遞歸呈現(xiàn)奔浅，所以我們只需針對第三種情況提出解決辦法。
4. 尋找橫跨中間位置的最大子數(shù)組可以將問題一分為二：我們確定中間元素诗良，在中間元素的左邊找最大的數(shù)組汹桦，右邊找到最大的數(shù)組，兩邊的最大子數(shù)組可以確定一個(gè)邊界鉴裹，使得整個(gè)橫跨數(shù)組為所有橫跨數(shù)組中最大的一個(gè)舞骆。
5. 遞歸尋找左右兩半部分的最大子數(shù)組。

code

首先是暴力解法：
max = LONG_MIN（int 最小值）
for( int i = 0 to A.length)
  sum = 0
  for(int j = i to A.length)
    sum = sum + A[j]
    if(sum > max)
      max = sum
      low = i
      high = j
return (low, high, max)

Result模型
@property (assign, nonatomic) NSInteger low;
@property (assign, nonatomic) NSInteger high;
@property (assign, nonatomic) NSInteger sum;
- (instancetype)initWithLow:(NSInteger)low High:(NSInteger)high Sum:(NSInteger)sum;

獲取子數(shù)組遞歸
- (Result *)getMaxSubArray:(NSArray *)array low:(NSInteger)low 
high:(NSInteger)high{
    if (high == low) {
        return [[Result alloc] initWithLow:low High:high Sum:[[array objectAtIndex:low] integerValue]];
    }
    else{
        NSInteger mid = (low + high)/2;
        Result *left = [self getMaxSubArray:array low:low high:mid];
        Result *right = [self getMaxSubArray:array low:mid + 1 high:high];
        Result *sub = [self getMaxCrossArray:array low:low mid:mid high:high];
        if (left.sum >= sub.sum && left.sum >= right.sum) {
            return left;
        }
        else if (right.sum >= sub.sum && right.sum >= left.sum){
            return right;
        }
        else{
            return sub;
        }
    }
}

獲取跨越子數(shù)組
- (Result *)getMaxCrossArray:(NSArray *)array low:(NSInteger)low mid:(NSInteger)mid high:(NSInteger)high{
    NSInteger left_sum = LONG_MIN;
    NSInteger sum = 0;
    NSInteger max_left = mid;
    for (NSInteger i = mid; i >= low; i--) {
        sum = sum + [[array objectAtIndex:i] integerValue];
        if (sum > left_sum) {
            left_sum = sum;
            max_left = i;
        }
    }
    
    NSInteger right_sum = LONG_MIN;
    sum = 0;
    NSInteger max_right = mid + 1;
    for (NSInteger i = mid + 1; i <= high; i++) {
        sum = sum + [[array objectAtIndex:i] integerValue];
        if (sum > right_sum) {
            right_sum = sum;
            max_right = i;
        }
    }
    
    sum = left_sum + right_sum;
    return [[Result alloc] initWithLow:max_left High:max_right Sum:sum];
}