Algorithm - Max Subsequence Sum (C)

末蓝、 2023-01-16 11:24 98阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.captainbed.net]

/*
     * MaxSubsequenceSum.c - by FreeMan
     */
    
    #include <stdio.h>
    
    #define NlogNAlgorithm
    
    #ifdef CubicAlgorithm
    int MaxSubsequenceSum(const int A[], int N)
    {
        int ThisSum, MaxSum, i, j, k;
        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;
                }
            }
        }
        return MaxSum;
    }
    #endif
    
    #ifdef QuadraticAlgorithm
    int MaxSubsequenceSum(const int A[], int N)
    {
        int ThisSum, MaxSum, i, j;
        MaxSum = 0;
        for (i = 0; i < N; i++)
        {
            ThisSum = 0;
            for (j = i; j < N; j++)
            {
                ThisSum += A[j];
                if (ThisSum > MaxSum)
                {
                    MaxSum = ThisSum;
                }
            }
        }
        return MaxSum;
    }
    #endif
    
    #ifdef NlogNAlgorithm
    static int Max3(int A, int B, int C)
    {
        return A > B ? A > C ? A : C : B > C ? B : C;
    }
    
    static int MaxSubSum(const int A[], int Left, int Right)
    {
        int MaxLeftSum, MaxRightSum;
        int MaxLeftBorderSum, MaxRightBorderSum;
        int LeftBorderSum, RightBorderSum;
        int Center, i;
    
        if (Left == Right) /* Base case */
        {
            if (A[Left] > 0)
            {
                return A[Left];
            }
            else
            {
                return 0;
            }
        }
    
        Center = (Left + Right) / 2;
        MaxLeftSum = MaxSubSum(A, Left, Center);
        MaxRightSum = MaxSubSum(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 MaxSubsequenceSum(const int A[], int N)
    {
        return MaxSubSum(A, 0, N - 1);
    }
    #endif
    
    #ifdef LinearAlgorithm
    int MaxSubsequenceSum(const int A[], int N)
    {
        int ThisSum, MaxSum, j;
        ThisSum = MaxSum = 0;
        for (j = 0; j < N; j++)
        {
            ThisSum += A[j];
            if (ThisSum > MaxSum)
            {
                MaxSum = ThisSum;
            }
            else if (ThisSum < 0)
            {
                ThisSum = 0;
            }
        }
        return MaxSum;
    }
    #endif
    
    main()
    {
        static int A[] = { 4, -3, 5, -2, -1, 2, 6, -2 };
        printf("Maxsum = %d\n", MaxSubsequenceSum(A, sizeof(A) / sizeof(A[0])));
        return 0;
    }
    
    // Output:
    /*
    Maxsum = 11
    
    */

[http_www.captainbed.net]: http://www.captainbed.net/troubleshooter