1最大子序列和

最大子序列和

1.O(n^2)

算法的核心是遍历每一个数字作为开始的所有子序列。定义一个最大值和一个当前子序列和的临时存储。一旦临时值超过最大值，则更新最大值。

根据上述描述，首先有一个外层循环，用于遍历每一个开始的数字。内层循环是以当前数字开始不停加入后续数字，加入后更新临时值，并以此更新最大值。

int MaxSubSequenceSum(const int A[], int n)
{
    int MaxSum = 0, temp_Sum = 0;
    for(int i = 0;i < N;i++ )
    {
        temp_Sum = 0;
        for(int j = 0;j < N;j++ )
        {
            temp_Sum+=A[j];
            if(temp_Sum > MaxSum)
                MaxSum = temp_Sum;
        }
    }
}

优化的可能设想：如果在以当前数字开头的子序列和已经小于0了，即使后续能出现超过MaxSum的子序列和，也应该直接continue，因为这个子序列大可以去掉前面小于0的序列部分达到更大的和值。这个和值序列必然是以之前小于0的序列后第一个大于0的数字作为开头的序列。

//优化代码
int MaxSubSequenceSum(const int A[], int n)
{
    int MaxSum = 0, temp_Sum = 0;
    for(int i = 0;i < N;i++ )
    {
        temp_Sum = 0;
        for(int j = 0;j < N;j++ )
        {
            temp_Sum+=A[j];
            if(temp_Sum<=0)
                continue;		//优化的地方
            if(temp_Sum > MaxSum)
                MaxSum = temp_Sum;
        }
    }
}

这个优化并没有减少最坏情况下的时间复杂度，只是在一定程度上做了剪枝来减少了部分常数级时间。

2.O(NlogN)

这个算法使用了分治的思想，核心为：将当前的序列分为前半和后半两部分。如果存在最大值，则必为下列三种情况之一：

1.最大值序列在前半部分

2.最大值序列在后半部分

3.最大值是前半部分和后半部分的最大值序列加上中间连接部分的副作用（中间夹的序列）

那么，只要从上述三种情况中直接比较出哪个最大，返回即可。

问题是：如何确定前半或后半的最大值序列呢？

答案是：

1.分治为最小的一个单元进行时，只要这个单元值大于0，必然可以直接作为最大子序列和返回。（归纳的第一步成立）

2.如果不是最小的一个单元，则一定可以从左边最大，右边最大，横跨中间最大中找出最大的子序列和，作为上级调用的左边或右边最大子序列和，返回。（归纳的第二步）

如何知道横跨中间的最大值？

答案是使用第一种算法（但只需测试两个数，无需所有数字），将当前序列分为两半，每一份都从中间向两边测试以中间两个数字为开头或结尾最大子序列和。最后找到两个最大和，将其加在一起，即为所求最大和。

int Max(int a, int b, int c)
{
    int max = a;
    if (max < b)
        max = b;
    if (max < c)
        max = c;
    return max;
}

int MaxSubSum(const int A[], int left, int right)
{
    if (left == right)
        if (A[left] > 0)
            return A[left];
        else
            return 0;
    int centre = (left + right) / 2;
    int leftMax = MaxSubSum(A, left, centre);
    int rightMax = MaxSubSum(A, centre + 1, right);

    int left_temp_Max = 0, left_C_Max = 0;
    int right_temp_Max = 0, right_C_Max = 0;
    for (int i = centre; i >= left; i--)
    {
        left_temp_Max += A[i];
        if (left_temp_Max > left_C_Max)
            left_C_Max = left_temp_Max;
    }
    for (int i = centre + 1; i <= right; i++)
    {
        right_temp_Max += A[i];
        if (right_temp_Max > right_C_Max)
            right_C_Max = right_temp_Max;
    }
    return Max(right_C_Max + left_C_Max, leftMax, rightMax);
}

int MaxSubSequenceSum(int A[], int N)	//这个是对递归算法的封装，可以少一个参数0
{
    return MaxSubSum(A,0,N);
}

算法的时间复杂度分析：F(n) = 2F(n/2) + O(n) ，由此递推关系式算出时间复杂度为O(NlogN)

3.O(n)

这个算法的做法是遍历这个序列数组，设置一个最大值和临时存储的最大值。每递增一个，临时值更新，并以此更新最大值。如果临时值小于0，则临时指重置为0（隐含了放弃之前的序列，以当前数字重新作为下一个计算序列的开始）。

关于为什么不需要遍历测试每个数字作为开始：

1.如果某个数字作为开始，并且前面的序列和大于0，那么加上前面的序列一定比当前数字作为开始的子序列和要大。因此以这个数字作为开头的子序列被包含到前面大于0的子序列加上这个子序列里，无需测试。

2.如果某个数字作为开始，并且前面的序列和小于0，那么加上前面的序列一定比当前数字作为开始的子序列和要小，直接舍弃前面的序列，以当前数字作为开始测试即可，体现在程序里就是临时值被重置。

看起来没有测试每个数字开始，实际上隐含地测试过了。

int MaxSubSequenceSum(int A[], int N)
{
    int temp_Max = 0;
    int Max = 0;
    for(int i = 0; i<N ; i++)
    {
        temp_Max += A[i];
        
        if(temp_Max < 0)
            temp_Max = 0;
        if(temp_Max > Max)
            Max = temp_Max;
    }
    return Max;
}

发布于 2024-11-10