经典的求最大连续子数组和，以下有两种方法。

方法一：动规，复杂度O（n）

一遍扫描，R[i]表示以第i个元素结尾的最大连续子数组和，那么R[i+1] = max(A[i+1], R[i]+A[i+1])。代码如下：

int maxSubArray(int A[], int n) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        int i;        int max = A[0];        int tmp = A[0];        for(i = 1; i < n; i++){            if(tmp <= 0){                tmp = A[i];            }            else{                tmp += A[i];            }            if(tmp > max)                max = tmp;        }        return max;    }

方法二：分治的方法，把数组从中间分开，那么最大和有三种情况：全在左边，全在右边，两边都有。复杂度为O（nlgn）。

int maxSubArray(int A[], int left, int right){        if(left == right){            return A[left];        }        int middle = (left + right)/2;        int maxLeft = maxSubArray(A, left, middle);        int maxRight = maxSubArray(A, middle+1, right);        int maxToLeftBorder = A[middle];        int i,tmp=0;        for(i = middle; i >= 0; i--){            tmp += A[i];            if(tmp > maxToLeftBorder)                maxToLeftBorder = tmp;        }        int maxToRightBorder = A[middle + 1];        tmp = 0;        for(i = middle+1; i < right; i++){            tmp += A[i];            if(tmp > maxToRightBorder)                maxToRightBorder = tmp;        }        int max1 = maxLeft>maxRight?maxLeft:maxRight;        int max2 = maxToLeftBorder+maxToRightBorder;        return max1>max2?max1:max2;    }    int maxSubArray(int A[], int n) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        return maxSubArray(A, 0, n-1);    }