最大子序列问题

问题描述：对于一个无序序列q=，存在一个子序列q0=，使得该子序列的和最大，求该子序列和的值maxNum。

算法实现：

#include 
using namespace std;

//算法1，时间复杂度：o(n`3)
int max_subSeq1 (int a[], int len) {
	
	int i, j, k;
	int maxNum=0;
	int thisNum=0;
	
	for (i=0; imaxNum) {
				maxNum = thisNum;
			}
		}
	}
	
	return maxNum;
	
}



//算法2，时间复杂度：o(n`2)
int max_subSeq2 (int a[], int len) {
	
	int i, j;
	int maxNum=0;
	int thisNum=0;
	
	for (i=0; imaxNum){
				maxNum = thisNum;
			}
		}
	}
	
	return maxNum;
}



//算法3，时间复杂度：o(n*logn)
int max3 (int a, int b, int c) {
	if (a>b && a>c) return a;
	else if (b>a && b>c) return b;
	else return c;
}

int max_subSeq3 (int a[], int left, int right) {
	
	int leftMaxNum, rightMaxNum;
	int leftMaxBorder, rightMaxBorder;
	int leftBorder, rightBorder;
	int center;
	int i;
	
	if (left==right) {
		
		if (a[left]>0) {
			return a[left];
		}
		
		else{
			return 0;
		}
	}
	
	center = (left+right)/2;
	
	leftMaxNum = max_subSeq3(a, left, center);
	rightMaxNum = max_subSeq3(a, center+1, right);
	
	leftBorder=0;
	leftMaxBorder=0;
	
	for (i=center; i>=left; i--){
		
		leftBorder += a[i];
		
		if (leftBorder>leftMaxBorder) {
			leftMaxBorder = leftBorder;
		}
	}
	
	rightBorder = 0;
	rightMaxBorder = 0;
	
	for (i=center+1; i<=right; i++) {
		
		rightBorder += a[i];
		
		if (rightBorder>rightMaxBorder) {
			rightMaxBorder = rightBorder;
		}
	}
	
	return max3(leftMaxNum, rightMaxNum, leftMaxBorder+rightMaxBorder);
}



//算法4，时间复杂度：o(n)
int max_subSeq4 (int a[], int len) {
	
	int i;
	int maxNum=0;
	int thisNum=0;
	
	for (i=0; imaxNum) {
			maxNum = thisNum;
		}
		
		if (thisNum<0) {
			thisNum = 0;
		}
	}
	
	return maxNum;
	
}
	
	
	
int main(){
	
	int a[] = {1,-2,3,8,-6,-10,9,-2,-8,6,8,-10,9,12,-11,14,-3,1};
	int *p = &a[0];
	int len = sizeof(a)/sizeof(a[0]);
	
	cout << max_subSeq1(p,len) << endl;
	cout << max_subSeq2(p,len) << endl;
	cout << max_subSeq3(p,0,len-1) << endl;
	cout << max_subSeq4(p,len) << endl;
	
	return 0;
}

算法3和算法4要求都要掌握！