#include
#include

using?namespace?std;

int?MaxSubseqSum1（int*?A?int?N）;
int?MaxSubseqSum2（int*?A?int?N）;
int?MaxSubseqSum3（int*?A?int?N）;

int?MaxSubseqSum4（int*?A?int?N）;
int?GetBorderSubseqSum（int*?A?int?left?int?right）;

int?main（）
{
	int?maxNum?=?0;
	int?nNum?=?0;		//輸入數(shù)據(jù)的個(gè)數(shù)
	cout?<	cin>>nNum;
	int?*pNum?=?new?int[nNum];

	//循環(huán)輸入nNum個(gè)數(shù)
	for（int?i=0;i		cin>>pNum[i];

	clock_t?tStarttStop;
	tStart?=?clock（）;		//起始時(shí)間
	//算法執(zhí)行1000次
	for（int?i=0;i<1000;i++）
		for（int?i=0;i<10000;i++）
			maxNum?=?MaxSubseqSum1（pNum?nNum）;
	tStop?=?clock（）;		//結(jié)束時(shí)間

	cout?<	cout?<	cin.get（）;
	cin.get（）;
	return?0;

}


//暴力求解
//時(shí)間復(fù)雜度為：?N*N*N
int?MaxSubseqSum1（int*?A?int?N）
{
	int?thisNum=0?maxSum=0;
	//左邊起始端
	for（int?i=0;i	{
		//右邊起始端
		for（int?j=i;j		{
			thisNum?=0;
			//索引到中間的每個(gè)數(shù)據(jù)
			for（int?k=i;k<=j;k++）
				thisNum?+=A[k];
			if（thisNum>maxSum）
				maxSum?=?thisNum;
		}
	}
	return?maxSum;
}

//復(fù)雜度為N*N的算法
int?MaxSubseqSum2（int*?A?int?N）
{
	int?thisNum=0?maxSum=0;
	//左邊起始端
	for（int?i=0;i	{
		thisNum?=?0;	//左邊起始端每變化一次，將thisNum置0一次
		//右邊起始端
		for（int?j=i;j		{
			thisNum+=A[j];
			if（thisNum>maxSum）
				maxSum?=?thisNum;
		}
	}
	return?maxSum;
}

//在線處理算法時(shí)間復(fù)雜度為N
int?MaxSubseqSum3（int?*A?int?N）
{
	int?thisNum=0?maxSum=0;
	for（int?i=0;i	{
		thisNum+=A[i];
		if（thisNum>maxSum）
			maxSum?=?thisNum;
		//如果當(dāng)前和小于0，則將其丟棄置0，因?yàn)槠鋵?duì)后面沒(méi)有作用，只能使后面的更小
		else?if（thisNum<0）
			thisNum?=0;
	}
	return?maxSum;
}

//分為治之的思想
//時(shí)間復(fù)雜度為N*logN
int?MaxSubseqSum4（int*?A?int?N）
{
	//獲取左右邊界
	int?left?=?0?right?=?N-1;

	//只有一個(gè)元素
	if（left?==?right）
	{
		if（A[left]<0）
			return?0;
		else
			return?A[left];
	}

	return?GetBorderSubseqSum（A?left?right）;
}

//將一個(gè)小的子列塊求其最大列和
//該函數(shù)是一個(gè)遞歸調(diào)用的函數(shù)
int?GetBorderSubseqSum（int*?A?int?left?int?right）
{
	//只有一個(gè)元素
	if（left?==?right）
	{
		if（A[left]<0）
			return?0;
		else
			return?A[left];
	}
	//獲取邊界
	int?mid?=?（left+right）/2;
	int?nBorderMaxSum?=?0;		//左右最大列和值

	//獲取左右兩快中最大和數(shù)
	int?nMaxLeftNum?=?GetBorderSubseqSum（A?left?mid）;
	int?nMaxRightNum?=?GetBorderSubseqSum（A?mid+1?right）;

	//考慮中間這一一種情況
	//1向左檢索
	int?nTempMaxLeftSum?=0;		//左邊檢索的最大和值
	int?nLeftSum=0;
	for（int?i=mid;i>=left;i--）
	{
		nLeftSum?+=A[i];
		if（nLeftSum>nTempMaxLeftSum）
			nTempMaxLeftSum=nLeftSum;
	}

	//2、向右檢索
	int?nTempMaxRightSum?=0;		//右邊檢索的最大和值
	int?nRightSum=0;
	for（int?i=mid+1;i<=right;i++）
	{
		nRightSum?+=A[i];
		if（nRightSum>nTempMaxRightSum）
			nTempMaxRightSum=nRightSum;
	}

	nBorderMaxSum?=?nTempMaxLeftSum+nTempMaxRightSum;

	//對(duì)nBorderMaxSum、nMaxLeftNum、nMaxRightNum三者取最大的
	if（nMaxLeftNum>=nMaxRightNum）
	{
		if（nMaxLeftNum>=nBorderMaxSum）
			return?nMaxLeftNum;
		else
			return?nBorderMaxSum;
	}

	else
	{
		if（nMaxRig

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件??????66560??2017-03-10?10:07??Project2\Debug\Project2.exe

?????文件?????586128??2017-03-10?10:07??Project2\Debug\Project2.ilk

?????文件?????838656??2017-03-10?10:07??Project2\Debug\Project2.pdb

?????文件????????532??2017-03-10?10:07??Project2\Project2\Debug\cl.command.1.tlog

?????文件???????8990??2017-03-10?10:07??Project2\Project2\Debug\CL.read.1.tlog

?????文件????????360??2017-03-10?10:07??Project2\Project2\Debug\CL.write.1.tlog

?????文件??????????2??2017-03-10?10:07??Project2\Project2\Debug\link-cvtres.read.1.tlog

?????文件??????????2??2017-03-10?10:07??Project2\Project2\Debug\link-cvtres.write.1.tlog

?????文件??????????2??2017-03-10?10:07??Project2\Project2\Debug\link-rc.read.1.tlog

?????文件??????????2??2017-03-10?10:07??Project2\Project2\Debug\link-rc.write.1.tlog

?????文件??????????2??2017-03-10?10:07??Project2\Project2\Debug\link.12236-cvtres.read.1.tlog

?????文件??????????2??2017-03-10?10:07??Project2\Project2\Debug\link.12236-cvtres.write.1.tlog

?????文件??????????2??2017-03-10?10:07??Project2\Project2\Debug\link.12236-rc.read.1.tlog

?????文件??????????2??2017-03-10?10:07??Project2\Project2\Debug\link.12236-rc.write.1.tlog

?????文件??????????2??2017-03-10?10:07??Project2\Project2\Debug\link.12236.read.1.tlog

?????文件??????????2??2017-03-10?10:07??Project2\Project2\Debug\link.12236.write.1.tlog

?????文件???????1124??2017-03-10?10:07??Project2\Project2\Debug\link.command.1.tlog

?????文件???????2372??2017-03-10?10:07??Project2\Project2\Debug\link.read.1.tlog

?????文件????????472??2017-03-10?10:07??Project2\Project2\Debug\link.write.1.tlog

?????文件?????????75??2017-03-10?10:07??Project2\Project2\Debug\Project2.lastbuildstate

?????文件???????1325??2017-03-10?10:07??Project2\Project2\Debug\Project2.log

?????文件?????257024??2017-03-10?10:07??Project2\Project2\Debug\vc110.idb

?????文件?????339968??2017-03-10?10:07??Project2\Project2\Debug\vc110.pdb

?????文件?????154208??2017-03-10?10:07??Project2\Project2\Debug\源.obj

?????文件???????3311??2017-03-07?09:06??Project2\Project2\Project2.vcxproj

?????文件????????941??2017-03-07?09:06??Project2\Project2\Project2.vcxproj.filters

?????文件???????3366??2017-03-10?10:07??Project2\Project2\源.cpp

?????文件????7143424??2017-03-10?10:07??Project2\Project2.sdf

?????文件????????891??2017-03-07?08:54??Project2\Project2.sln

????..A..H.?????19968??2017-03-10?10:07??Project2\Project2.v11.suo

............此處省略7個(gè)文件信息