最大子段和C语言实现

求最大连续子段和

#include
using namespace std;
int test1[] = {-2, 11, -4, 13, -5, 2};
int test2[] = {-1, 3, -4, -2, 2, 2, -3};
int test3[] = {-1, -2, -4, -7, -3, -9};

int max(int a, int b){
	return a>b?a:b;
}

int three_times(int test[], int n){
	int ret = 0x80000000;
	for(int i = 0; i 
最多使用三层嵌套循环，时间复杂度无疑为O(N3)。
 
两层循环穷举 
#include
using namespace std;
int test1[] = {-2, 11, -4, 13, -5, 2};
int test2[] = {-1, 3, -4, -2, 2, 2, -3};
int test3[] = {-1, -2, -4, -7, -3, -9};

int max(int a, int b){
	return a>b?a:b;
}

int two_times(int test[], int n){
	int ret = 0x80000000;
	for(int i = 0; i 
分析方法同上，时间复杂度为O(n2)。
 
分治算法 
#include
using namespace std;
int test1[] = {-2, 11, -4, 13, -5, 2};
int test2[] = {-1, 3, -4, -2, 2, 2, -3};
int test3[] = {-1, -2, -4, -7, -3, -9};

int max(int a, int b){
	return a>b?a:b;
}

int sum12(int test[], int left, int right){
	int mid = (left+right)/2;
	int sum1=test[mid];
	int temp = sum1;
	for(int i=mid-1;i>left;i--){
		temp+=test[i];
		sum1 = max(sum1, temp);
	}
	int sum2=test[mid+1];
	temp=sum2;
	for(int i=mid+2;i 
“分”的部分为logn时间复杂度，求mid左右两边最大字段和为n时间复杂度，嵌套到一起是O(nlogn)的时间复杂度。
 
动态规划 
#include
using namespace std;
int test1[] = {-2, 11, -4, 13, -5, 2};
int test2[] = {-1, 3, -4, -2, 2, 2, -3};
int test3[] = {-2, -1, -4, -7, -3, -9};

int max(int a, int b){
	return a>b?a:b;
}

int moti(int test[], int n){
	int ret = test[0];
	int now = test[0];
	for(int i=1;i 
一个for循环走到底了，时间复杂度为O(n)。
 
前缀和 
#include
using namespace std;
int test1[] = {-2, 11, -4, 13, -5, 2};
int test2[] = {-1, 3, -4, -2, 2, 2, -3};
int test3[] = {-2, -1, -4, -7, -3, -9};

int max(int a, int b){
	return a>b?a:b;
}
int min(int a, int b){
	return a 
出现了两个循环，但是循环并未嵌套到一起，所以时间复杂度仍然是O(n)。