求解最大子序列算法及比较_给出求解最大单调子序列问题的算法

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include "../StopWath.h"
using namespace std;
 
 
int A[2000];
int N = sizeof(A) / sizeof(A[0]);
int Sum1, Sum2, Sum3, Sum4;
 
CStopWatch stopwatch;
double time1, time2, time3, time4;
int MaxSubsequenceSum1(const int A[], int N);
int MaxSubsequenceSum2(const int A[], int N);
 
int Max3(int  a, int b, int c);
static int MaxSubNum(const int A[], int left, int right);
int MaxSubsequenceSum3(const int A[], int N);
 
int MaxSubsequenceSum4(const int A[], int N);
 
int main(int argc, char** argv)
{
	srand((unsigned)time(NULL));
	for (int i = 0; i < N; i++)
		A[i] = (rand() % 100) - 150;
 
 
	Sum1 = MaxSubsequenceSum1(A, N);
	Sum2 = MaxSubsequenceSum2(A, N);
	Sum3 = MaxSubsequenceSum3(A, N);
	Sum4 = MaxSubsequenceSum4(A, N);
 
	cout << Sum1 << "  time:  " << time1 << endl;
	cout << Sum2 << "  time:  " << time2 << endl;
	cout << Sum3 << "  time:  " << time3 << endl;
	cout << Sum4 << "  time:  " << time4 << endl;
	system("pause");
	return 0;
}
 
 
int MaxSubsequenceSum1(const int A[], int N)
{
	int ThisSum, MaxSum, i, j, k;
 
	stopwatch.Start();
	MaxSum = 0;
	for (i = 0; i < N; i++)
	{
		for (j = i; j < N; j++)
		{
			ThisSum = 0;
			for (k = i; k <= j; k++)
				ThisSum += A[k];
 
			if (ThisSum > MaxSum)
				MaxSum = ThisSum;
		}
	}
 
	time1 = stopwatch.Stop();
	return MaxSum;
}
 
int MaxSubsequenceSum2(const int A[], int N)
{
	int ThisSum, MaxSum, i, j;
 
	stopwatch.Start();
	MaxSum = 0;
	for (i = 0; i < N; i++)
	{
		ThisSum = 0;
		for (j = i; j < N; j++)
		{
			ThisSum += A[j];
 
			if (ThisSum > MaxSum)
				MaxSum = ThisSum;
		}
	}
 
	time2 = stopwatch.Stop();
	return MaxSum;
}
 
static int MaxSubNum(const int A[], int left, int right)
{
	int MaxLeftSum, MaxRightSum;
	int MaxLeftBorderSum, MaxRightBorderSum;
	int LeftBorderSum, RightBorderSum;
	int Center, i;
 
	if (left == right)
	{
		if (A[left] > 0)
			return A[left];
		else
			return 0;
	}
 
 
	Center = (left + right) / 2;
	MaxLeftSum = MaxSubNum(A, left, Center);
	MaxRightSum = MaxSubNum(A, Center + 1, right);
 
	MaxLeftBorderSum = 0;
	LeftBorderSum = 0;
 
	for (i = Center; i >= left; i--)
	{
		LeftBorderSum += A[i];
		if (LeftBorderSum > MaxLeftBorderSum)
			MaxLeftBorderSum = LeftBorderSum;
	}
 
	MaxRightBorderSum = 0;
	RightBorderSum = 0;
 
	for (i = Center + 1; i <= right; i++)
	{
		RightBorderSum += A[i];
		if (RightBorderSum > MaxRightBorderSum)
			MaxRightBorderSum = RightBorderSum;
	}
 
	return Max3(MaxLeftSum, MaxRightSum, (MaxLeftBorderSum + MaxRightBorderSum));
}
 
int Max3(int  a, int b, int c)
{
	return (a > b) ? ((a > c) ? a : c) : ((b > c) ? b : c);
}
 
int MaxSubsequenceSum3(const int A[], int N)
{
	int MaxNum = 0;
 
	stopwatch.Start();
 
	MaxNum = MaxSubNum(A, 0, N - 1);
 
	time3 = stopwatch.Stop();
 
	return MaxNum;
}
 
int MaxSubsequenceSum4(const int A[], int N)
{
	int ThisSum, MaxSum, j;
 
	ThisSum = MaxSum = 0;
	stopwatch.Start();
	for (j = 0; j < N; j++)
	{
		ThisSum += A[j];
 
		if (ThisSum > MaxSum)
			MaxSum = ThisSum;
		else if (ThisSum < 0)
			ThisSum = 0;
	}
 
	time4 = stopwatch.Stop();
	return MaxSum;
}