求数组最大子序列的和

题目：给出数组{4,-3,5,-2,-1,2,6,-2}，求子序列的最大和。

分别用一下两种方法解决。

#include <stdio.h>
// 方法1： 分治法
//时间复杂度 O(NlogN)
int max3(int num1 , int num2 , int num3){
int max = num1;
if(max<num2)max= num2;
if(max<num3)max=num3;
return max;
}
int  maxSubSum(int array[],int start, int end){
int maxLeftSum , maxRightSum;
int maxLeftBorderSum,maxRightBorderSum;
int leftBorderSum,rightBorderSum;
int middle,i;

if(start == end){
if(array[start] >0)
return array[start];
else
return 0;
    }



    middle = (start+ end)/2;
//递归求解左半部分最大子序列和
    maxLeftSum = maxSubSum(array, start, middle);
//递归求解右半部分最大子序列和
    maxRightSum = maxSubSum(array, middle+1, end);

//求解中间部分的最大子序列和
    leftBorderSum=0,maxLeftBorderSum=0;
for(i = middle;i>=start;i--){
        leftBorderSum+=array[i];
if(leftBorderSum>maxLeftBorderSum)
            maxLeftBorderSum = leftBorderSum;
    }
    rightBorderSum =0,maxRightBorderSum=0;
for (i=middle+1; i<=end; i++) {
        rightBorderSum+=array[i];
if(rightBorderSum>maxRightBorderSum){
            maxRightBorderSum = rightBorderSum;
        }

    }
return max3(maxLeftSum, maxRightSum, maxLeftBorderSum+maxRightBorderSum);

}


//方法2 时间复杂度 o(N)

int getMaxSubSum(int array[],int start,int end){
int currentSum = 0, maxSum =0;
for(int i = start;i <=end;i++){
        currentSum+=array[i];
if(currentSum<0)
            currentSum= array[i];
if(currentSum>maxSum){
            maxSum = currentSum;
        }
    }
return maxSum;
}
int main(int argc, const char * argv[]) {
// insert code here...
int a[] = {4,-3,5,-2,-1,2,6,-2};
//int max = maxSubSum(a, 0, 7);
int max = getMaxSubSum(a, 0, 7);
printf("%d",max);
return 0;
}