最大子序列和

时间: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)