最大子序列和问题四种算法源代码

最大子序列和问题四种算法源代码

#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;		//输入数据的个数
	cout << “请输入数据个数：“ ;
	cin>>nNum;
	int *pNum = new int[nNum];

	//循环输入nNum个数
	for（int i=0;i		cin>>pNum[i];

	clock_t tStarttStop;
	tStart = clock（）;		//起始时间
	//算法执行1000次
	for（int i=0;i<1000;i++）
		for（int i=0;i<10000;i++）
			maxNum = MaxSubseqSum1（pNum nNum）;
	tStop = clock（）;		//结束时间

	cout << “算法执行时间：“ << （（tStop - tStart）/CLK_TCK*1.0/1000/10000） << endl;
	cout << “结果：“ << maxNum << endl;
	cin.get（）;
	cin.get（）;
	return 0;

}


//暴力求解
//时间复杂度为： 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;
			//索引到中间的每个数据
			for（int k=i;k<=j;k++）
				thisNum +=A[k];
			if（thisNum>maxSum）
				maxSum = thisNum;
		}
	}
	return maxSum;
}

//复杂度为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;
}

//在线处理算法时间复杂度为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;
		//如果当前和小于0，则将其丢弃置0，因为其对后面没有作用，只能使后面的更小
		else if（thisNum<0）
			thisNum =0;
	}
	return maxSum;
}

//分为治之的思想
//时间复杂度为N*logN
int MaxSubseqSum4（int* A int N）
{
	//获取左右边界
	int left = 0 right = N-1;

	//只有一个元素
	if（left == right）
	{
		if（A[left]<0）
			return 0;
		else
			return A[left];
	}

	return GetBorderSubseqSum（A left right）;
}

//将一个小的子列块求其最大列和
//该函数是一个递归调用的函数
int GetBorderSubseqSum（int* A int left int right）
{
	//只有一个元素
	if（left == right）
	{
		if（A[left]<0）
			return 0;
		else
			return A[left];
	}
	//获取边界
	int mid = （left+right）/2;
	int nBorderMaxSum = 0;		//左右最大列和值

	//获取左右两快中最大和数
	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;

	//对nBorderMaxSum、nMaxLeftNum、nMaxRightNum三者取最大的
	if（nMaxLeftNum>=nMaxRightNum）
	{
		if（nMaxLeftNum>=nBorderMaxSum）
			return nMaxLeftNum;
		else
			return nBorderMaxSum;
	}

	else
	{
		if（nMaxRig

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      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个文件信息