最近在看算法导论，看到计算最大子数组问题，于是写了一个iOS版本的。

1. 利用分治策略，逐层寻找
2. 最大子数组存在三种情况：若将数组在中间元素位置划分为两部分，则最大子数组可能在中间元素的左半部分、右半部分或者是跨越中间元素的部分。
3. 现在我们将问题一分为三，在左半部分寻找最大子数组，在右半部分寻找最大子数组，以及在横跨中间的最大子数组中寻找三者之中最大的。而左右两半部分的情况其实是以上情况的递归呈现，所以我们只需针对第三种情况提出解决办法。
4. 寻找横跨中间位置的最大子数组可以将问题一分为二：我们确定中间元素，在中间元素的左边找最大的数组，右边找到最大的数组，两边的最大子数组可以确定一个边界，使得整个横跨数组为所有横跨数组中最大的一个。
5. 递归寻找左右两半部分的最大子数组。

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;

获取子数组递归
- (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;
        }
    }
}

获取跨越子数组
- (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];
}