基础闯关记-最大子数组问题求解

# 最大子数组问题求解
## 问题描述
**问题**：输入一个整型数组，数据元素有正数也有负数，求元素组合成连续子数组之和最大的子数组。

**描述**：输入的数组为1, -2, 3, 10, -4, 7, 2, -5，最大和的连续子数组为3, 10, -4, 7, 2，其最大和为18。

## 暴力求解法
第一种解法最简单，最暴力，最容易理解的一种方法。这种解法的思想就是，从第一个元素开始，然后和后面的所有元素组合开有没有可能形成最大值。代码很简单
```
#include<stdio.h>
#define MAX_LEN 8

int main(){
    int arr[MAX_LEN] = {1, -2, 3, 10, -4, 7, 2, -5};
    int i,j;
    int sum = 0;
    for(i=0; i < MAX_LEN; i++){
        int _tmpSum = arr[i]; 
        for(j=i+1; j < MAX_LEN; j++){
            _tmpSum += arr[j];
            if(_tmpSum > sum){
                sum = _tmpSum;  
            }           
        }       
    }

printf("%d", sum);
}
```
这种算法的时间复杂度为O(n^2)。所以这种方法虽然简单，单一般不采用。
## 分治求解法
计算机领域经常使用的一种求解思想，分而治之。想想二分查找，一半一半得淘汰，这样效率会提高很多。我们同样也可以用这种思路求解最大子数组问题。假定我们要寻找数组A[low .. high]的最大子数组，使用分治技术我们将A划分为两个等规模子数组。首先找到数组A的中央位置，比如mid，然后分解成两个子数组A[low .. mid]和A[mid+1 .. high]。这样如果存在一个最大的子元素系列A[i .. j]那么它一定满足下面三种情况之一
```
1. 完全位于子数组A[low .. mid]中，此时low<=i<=j<=mid
2. 完全位于子数组A[mid+1 .. high]中，此时mid<i<=j<=high
3. 跨越了中点,此时low<=i<=mid<j<=high
```

这个过程可以用下面的图说明，假如我们要求解最大子数组，假设这个数字的中间位置mid，这个最大子数组肯定是left_max，mid_max，right_max中的一个，只要比较这三者的大小就可以了。求解mid左边的最大子数组问题又是一个递归的过程，又要找出mid左边的数组中left_max，mid_max，right_max。

![image](http://note.youdao.com/yws/api/personal/file/WEB575f687dd0116e8e96289ed699ccdb9b?method=download&shareKey=df1a3fa68fed33ad501a86f0fda58cdc)

分治法求解最大子数组函数框架，仔细观察者函数和上面图的关系。
```
int find_maximum_subarray(int *arr, int left, int right){
    if(left == right){
            return arr[left];
    }
    int mid = (left + right) / 2;
    int left_max = find_maximum_subarray(arr, left, mid);
    int right_max = find_maximum_subarray(arr, mid+1, right);
    int mid_max = find_max_crossing_subarray(arr, left, mid, right);

if(left_max > mid_max && left_max > right_max){
            return left_max;
    }else if(right_max > mid_max && right_max > mid_max){
            return right_max;
    }else{
            return mid_max;
    }
    return 1;
}
```

最后我们要实现跨越中间位置(mid)的最大子数组问题，既然已经确定肯定跨越了中间位置，可以从中间位置(mid)开始，向左和向分别求最大字数粗，然后将两者相加。最终结果就是跨越中间位置的最大子数组，如图所示

![image](http://note.youdao.com/yws/api/personal/file/WEBd72b1e366585119b04bef0ed5386fc7c?method=download&shareKey=e78e12ffe410f43d57b1a816edea072c)

求跨越中间位置最大子数组函数实现
```
int find_max_crossing_subarray(int *arr, int left, int mid, int right){
    int left_max = INT_MIN;
    int right_max = INT_MIN;

int i = mid;
    int tmp_left = 0;
    while(i >= left){
        tmp_left += arr[i];
        if(tmp_left > left_max){
            left_max = tmp_left;
        }
        i--;
    }

int j = mid +1; 
    int tmp_right = 0;
    while(j <= right){
        tmp_right += arr[j];
        if(tmp_right > right_max){
            right_max = tmp_right;
        }
        j++;
    }
    
    return left_max + right_max;
}
```

最后附上完整代码：
```
#include<stdio.h>
#include<limits.h>
int find_maximum_subarray(int *arr, int left, int right);
int find_max_crossing_subarray(int *arr, int left, int mid, int right);

int main(){
    int arr[8] = {1, -2, 3, 10, -4, 7, 2, -5};
    int max = find_maximum_subarray(arr, 0, 7);
    printf("%d", max);
}

int find_maximum_subarray(int *arr, int left, int right){
    if(left == right){
        return arr[left];
    }
    int mid = (left + right) / 2;
    int left_max = find_maximum_subarray(arr, left, mid);
    int right_max = find_maximum_subarray(arr, mid+1, right);
    int mid_max = find_max_crossing_subarray(arr, left, mid, right);

if(left_max > mid_max && left_max > right_max){
        return left_max;
    }else if(right_max > mid_max && right_max > mid_max){
        return right_max;
    }else{
        return mid_max;
    }
    return 1;
}

int find_max_crossing_subarray(int *arr, int left, int mid, int right){
    int left_max = INT_MIN;
    int right_max = INT_MIN;
    
    int i = mid;
    int tmp_left = 0;
    while(i >= left){
        tmp_left += arr[i];
        if(tmp_left > left_max){
            left_max = tmp_left;
        }
        i--;
    }

int j = mid +1; 
    int tmp_right = 0;
    while(j <= right){
        tmp_right += arr[j];
        if(tmp_right > right_max){
            right_max = tmp_right;
        }
        j++;
    }

return left_max + right_max;
}
```

Navigation

Recent Posts

Friend Links