最大子序列的和算法-时间复杂度O(n)

#include<iostream>
using namespace std;

int MaxSubseqSum(int ar[],int n){
	int ThisSum=0,MaxSum=0;
	for(int i=0;i<n;i++){
		ThisSum+=ar[i];
		if(ThisSum>MaxSum)
			MaxSum=ThisSum;
		else if(ThisSum<0)
			ThisSum=0;
	}
	return MaxSum;
}

int main(){
	int a[]={-1,3,-2,4,-6,1,6,-1,9,-7};
	int lena=sizeof(a)/sizeof(a[0]);
	cout<<MaxSubseqSum(a,lena);
	
	return 0;
}

利用分治算法(归并排序)的时间复杂度是O(n log n)