目录
  1. 题目描述
  2. 输入格式
  3. 输出格式
  4. 样例输入
  5. 样例输出
  6. 题解
    1. 方法①:暴力枚举法O(n^3)
      1. 稍微优化成O(n^2)
    2. 方法②:二分法 O(nlogn)
    3. 方法③ 动态规划O(n)
    4. 方法④ 另一种O(n)算法
PTA-最大连续子数列和(4种方法)

题目描述

给定K个整数组成的序列{ $N_1$​​ ,$N​_2$ , …, $N​_k$ },“连续子列”被定义为{ $N_i$​​ , $N_i+1$, …, $N_j$},其中 $1≤i≤j≤K$。“最大子列和”则被定义为所有连续子列元素的和中最大者。
现要求你编写程序,计算给定整数序列的最大子列和。

输入格式

输入第1行给出正整数n (≤100000);第2行给出n个整数,其间以空格分隔。

输出格式

在一行中输出最大子列和。如果序列中所有整数皆为负数,则输出0。

样例输入

1
2
6
-2 11 -4 13 -5 -2

样例输出

1
20






题解

方法①:暴力枚举法O(n^3)

最暴力的方法:用三层循环枚举所有的子数列,输出其中的最大值。

1
2
3
4
5
6
7
8
9
ans = 0;
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
{
sum = 0;
for(int k = i; k <= j; k++)
sum += num[k];
if(sum > ans) ans = sum;
}

稍微优化成O(n^2)

可以注意到:设sum(i)为从 a~1~ 到 a~i~ 的数列的和,sum(0)为0,则从 a~i~ 到 a~j~ 的子数列的和为sum( j ) - sum( i-1 )
由此,可以将暴力枚举法的三层循环改为二层循环:

1
2
3
4
5
ans = 0;
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
if(sum[j] - sum[i-1] > ans)
ans = sum[j] - sum[i-1]

方法②:二分法 O(nlogn)

首先,我们可以把整个序列平均分成左右两部分,答案则会在以下三种情况中:
1、所求序列完全包含在左半部分的序列中。
2、所求序列完全包含在右半部分的序列中。
3、所求序列刚好横跨分割点,即左右序列各占一部分。
前两种情况和大问题一样,只是规模小了些,如果三个子问题都能解决,那么答案就是三个结果的最大值。

前两种情况都比较好解决,需要注意的是第三种情况怎么处理:
以分割点为起点向左的最大连续序列和、以分割点为起点向右的最大连续序列和,这两个结果的和就是第三种情况的答案。因为起始点(分割点)是固定的,所以两者只需要O(n)以内的复杂度得出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
long long solve(int left, int right)
{
int mid = (left + right) / 2;
//处理第三种情况
long long suml, sumr, maxl, maxr;
suml = sumr = maxl = maxr = 0;
for(int i = mid; i > 0; i--)
{
suml += num[i];
if(suml>maxl) maxl = suml;
}
for(int i = mid+1; i < n; i++)
{
sumr += num[i];
if(sumr>maxr) maxr = sumr;
}
long long ans = maxr + maxl;

long long lans = solve(left, mid), rans = solve(mid+1, right); //处理左右两段
ans = max(ans, lans); ans = max(ans, rans); //返回最大值
return ans;
}

方法③ 动态规划O(n)

终极王牌方法,找到一个合适的公式,可以很快解决问题。
根据连续子数列的连续这一性质,我们可以设dp[i]为以num[i]结尾的最大子数列和,则有

而最终答案则是: $max(dp[i]),i\in[1, n]$

1
2
3
4
5
6
7
8
dp[0] = 0; 
long long ans = 0;
for(int i = 1; i <= n; i++)
{
dp[i] = max(dp[i-1], 0) + num[i];
if(dp[i] > ans) ans = dp[i];
}
cout << ans;

方法④ 另一种O(n)算法

由暴力法的前缀和法得到启发:以num[i]结尾的某个子数列和,是sum[i] - sum[j](j < i),则以num[i]结尾的子数列和,是sum[i] - sum[ j-1 ],其中sum[ j-1 ]为sum[0], sum[1] , …, sum[ i-1 ]中的最小值。
则我们只需要在一次遍历中维护之前的最小的sum不断更新答案即可。

1
2
3
4
5
6
7
long long minsum = 0, ans = 0, sum = 0;
for(int i = 1; i <= n; i++)
{
sum += num[i];
if(sum - minsum > ans) ans = sum - minsum;
if(sum < minsum) minsum = sum;
}
文章作者: Irimsky
文章链接: /2019/07/29/PTA-最大连续子数列和(4种方法)/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Irimsky's Blog

评论