求解最大子序列算法及比较

谁践踏了优雅 2022-08-02 06:22 177阅读 0赞

#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;
    }

![SouthEast][]

**第一种算法最慢，其次第二、第三种算法，最快的是第四中算法。**

**算法的详细描述见《数据结构与算法分析 C语言描述》**

[SouthEast]: /images/20220731/3cc8c106d1e04a7eba21aeb77b9c6bde.png