最大子数组问题

问题分析：在一个长为ｎ的数组Ａ[1..n]中，找到这样的i、j，使Ａ[i...j]中元素的和最大，称Ａ[i...j]为最大子数组。

算法一（分治思想）：

数组Ａ[low...high]的最大子数组必然满足三种情况：

１）子数组在Ａ[low...mid]中；

２）子数组在Ａ[mid+1,high]中；

３）子数组跨越中点mid。

因此可以使用递归分治方法计算find_max(A, low,  high)，其中满足：

find_max(A, low, high)　＝　max(find_max(A, low, mid), find_max(A, mid+1, high), cross_max(A, low, mid,  high))

cross_max(A, low, mid, high)是为了找到子数组跨越中点时的最大情况。

使用c++实现，代码如下：

#include<iostream>
using namespace std;
#define len 10
//定义输出信息数据结构，输出子数组左右下标，以及元素和
typedef struct info{
    　　int low;
    　　int high;
    　　int sum;
}*Info, Info1;
//创建输出结构info
Info createinfo(int A[], int low, int high){
    　　Info info = new Info1;
    　　int sum = 0;
    　　for (int i=low;i<=high;i++)
        　　sum += A[i];
    　　info->low = low;
    　　info->high = high;
    　　info->sum = sum;
    　　return info;
}
//子数组跨越中点时的最大情况
Info find_cross_max(int A[], int low, int mid, int high){
    　　int left_sum = A[mid];
    　　int right_sum = A[mid+1];
    　　int sum = 0;
    　　int left=mid;
    　　int right=mid+1;
    　　for(int i=mid;i>=low;i--){
        　　　　sum += A[i];
        　　　　if(sum > left_sum){   //这里不用>=，得到的结果是长度最短的最大子数组；使用>=得到的是最长的最大子数组
            　　　　left_sum = sum;
            　　　　left = i;
        　　　　}
    　　}
    　　sum = 0;
    　　for(int i=mid+1;i<=high;i++){
        　　　　sum += A[i];
        　　　　if(sum > right_sum){
            　　　　right_sum = sum;
            　　　　right = i;
        　　　　}
    　　}
    　　return createinfo(A, left, right);
}
//递归调用该函数，用分治法寻找最大子数组
Info find_maximum_subarray(int A[], int low, int high){
　　if(high == low)
        　　　　return createinfo(A, low, high);
    　　else{
        　　　　int mid = (low + high) / 2;
        　　　　Info left_info = find_maximum_subarray(A, low, mid);
        　　　　Info right_info = find_maximum_subarray(A, mid+1, high);
        　　　　Info cross_info = find_cross_max(A, low, mid, high);
        　　　　if (left_info->sum >= right_info->sum && left_info->sum >= cross_info->sum)
            　　　　　　return left_info;
        　　　　else if (right_info->sum >= left_info->sum && right_info->sum >= cross_info->sum)
            　　　　　　return right_info;
        　　　　else
            　　　　　　return cross_info;
    　　}
}
int main(){
    　　int A[len] = {2,5,1,8,-5,8,0,0,-9,8};
    　　Info max_subarray = find_maximum_subarray(A, 0, 9);
　　out<<"左下标为:"<<max_subarray->low<<endl<<"右下标为:"<<max_subarray->high<<endl<<"子数组大小为:"<<max_subarray->sum<<endl;
    　　return 0;
}

算法二（线性复杂度）：

对于数组Ａ[1...n]，从左到右遍历数组，记录目前为止处理过的最大子数组，直到遍历完整个数组，具体思路如下：

对于1<=j<=n，记录Ａ[1...j]的最大子数组和最大Ａ[i...j]的值，那么Ａ[1...j+1]的最大子数组为下面３种情况之一，取最优即可：

１）Ａ[1...j]的最大子数组

２）Ａ[i...j]＋Ａ[j+1]

３）Ａ[j+1]

具体c++程序实现：

#include<iostream>
#define len 10
using namespace std;

void find_max_array(int A[],int low,int high){
    int left1=0,right1=0,sum1=A[low];
    int left2=0,right2=0,sum2=A[low];
    for(int i=low+1;i<=high;i++){
        if(sum2<=0){
            left2 = i;
            right2 = i;
            sum2 = A[i];
        }
        else{
            right2 = i;
            sum2 = sum2+A[i];
        }
        if(sum1<sum2){
            left1 = left2;
            right1 = right2;
            sum1 = sum2;
        }
    }
    cout<<"左下标为："<<left1<<endl;
    cout<<"右下标为："<<right1<<endl;
    cout<<"子数组和为："<<sum1<<endl;
}

int main(){
    int A[len] = {2,5,1,8,-5,8,0,0,-9,8};
    find_max_array(A,0,len-1);
    return 0;
}

总结：分治方法可能会得到算法复杂度低于暴力求解的算法，对于某些问题，分治策略虽然能给出较优算法，但不使用该策略甚至可以能做得更好，该问题就是很好的例子。