最大子序列和

时间：2021-01-06 00:45:28

最大子序列和

穷举法

int MaxSubSequenceSum(const int A[], int N)
{
int max_sum = 0;
//穷举所有的子序列
for (int i = 0; i < N; i++)
    {
for (int j = i; j < N; j++)
        {
//计算子序列的和
int cur_sum = 0;
for (int k = i; k <= j; k++)
            {
                cur_sum += A[k];
            }

if (cur_sum > max_sum)
                max_sum = cur_sum;
        }
    }
return max_sum;
}

算法说明：穷举所有的子序列，取最大和。
时间复杂度：第1个循环的大小为N，第二个循环的大小为N-i，但也可能是N，假设最坏的情况为N，同理，第三层循环也为N，总的时间复杂度为O(N^3)。

穷举法改进

int MaxSubSequenceSum(const int A[], int N)
{
int max_sum = 0;
for (int i = 0; i < N; i++)
    {

int cur_sum = 0;
for (int j = i; j < N; j++)
        {
            cur_sum += A[j];
if (cur_sum > max_sum)
                max_sum = cur_sum;
        }
    }
return max_sum;
}

算法说明：改进了穷举法的内层循环。
时间复杂度： O(N^2)

分治法

int MaxSubSequenceSum(const int A[], int N)
{
   MaxSubSum(A, 0, N-1);
}

int MaxSubSum(const int A[], int left, int right)
{
if(left == right)
    {
return A[left];
    }
//数组分为两部分
int mid = (left + right) / 2;
//左边部分的最大和
int left_max = MaxSubSum(A, left, mid);
//右边部分的最大和
int right_max = MaxSubSum(A, mid+1, right);
//跨越中间的最大和
int mid_left_max = 0;
int mid_right_max = 0;
int mid_left_sum = 0;
int mid_right_sum = 0;
int i = 0;
for(i=mid; i>=0; i--)
    {
       mid_left_sum += A[i];
if(mid_left_sum>mid_left_max)
        mid_left_max = mid_left_sum;
    }
for(i=mid+1; i<right; i++)
    {
       mid_right_sum += A[i];
if(mid_right_sum>mid_right_max)
        mid_right_max = mid_right_sum;
    }
int mid_max = mid_left_max+mid_right_max;

//返回三个部分的最大值
int tmp = left_max>right_max?left_max:right_max;
return tmp > mid_max ? tmp : mid_max;
}

算法说明： 将数组分为两个部分，最大子序列和可能出现在左侧，也可能出现在右侧，也可能跨越左右两个部分。
时间复杂度： 假设MaxSubSum(N)的运行时间为T(N)，左侧部分的运行时间T(N/2)，右侧部分的运行时间T(N/2)，中间部分的运行时间是O(N)；T(N) = 2*T(N/2)+O(N).即O(N log N)。

联机算法

int MaxSubSequenceSum(const int A[], int N)
{
int max = 0;
int sum = 0;

for (int i = 0; i < N; i++)
    {
sum += A[i];

if(sum > max)
        {
            max = sum;
        }
else if(sum < 0)
        {
sum = 0;
        }
    }

return max;
}

算法说明:
两点必须理解的前提：

  • 最大子序列的第一个元素不会是负的。即，如果a[i]是负的，那么它不可能是最大子序列的起点。因为任何用a[i]开头的序列，此时都不如用a[i+1]开头的序列和大。

  • 同理，任何负的子序列都不可能是最优子序列的前缀。

通过代码可以明显的看出，max，sum，初始化为0。在循环中，程序会从数组的第一个元素，找到第一个不为0的元素，然后将后面的元素不断的累加到sum中，直到sum小于0，sum重置为0。
假设其中的某个子序列a[i…j], a[i]>0,a[j]是第一个使这个子序列的和为负的元素。
重点解释两点：

  • 子序列A[i…j]的最大子序列和是多少

  • 对于任意 i < p <= j < k，会不会存在A[p]…A[K],构成最大子序列和。

对于第一点，因为a[j]是第一个使这个子序列的和为负的元素，所以对于任意i < p <= q <= j

  A[i]+A[i+1]+···+A[p-1]>0,
A[p]+A[i+1]+···+A[q] < A[i]+A[i+1]+···+A[p-1]+A[p]+···+A[q]

即，对于从p开始的任意子序列的和，都不如这个序列再加上a[i]到a[p-1]这个序列的和大。也就是说，A[i…j]的最大子序列和为 max(a[i], a[i]+a[i+1], a[i]+a[i+1]+a[i+2], …, a[i]+···a[j])。对应第一个 if 分支。

对于第二点，

  A[i]+A[i+1]+···+A[j] = (A[i]+A[i+1]+···+A[p-1]) + (A[p]+A[i+1]+···+A[j]) < 0,
A[i]+A[i+1]+···+A[p-1]>0,
A[p]+A[i+1]+···+A[j] < 0

因为任何负的子序列都不可能是最优子序列的前缀。故 A[p]+A[i+1]+···+A[j]不会是最大子序列的前缀。对应第二个 if 分支。

通过以上分析。数组最大子序列和 要么是 子序列*A[i…j]的最大子序列和*（第一个if分支）， 要么是从a[j+1]开始的新的数组的最大子序列和（第二个if分支）。

时间复杂度： O(N)

标签：

相关文章