原命题：中国大学MOOC 2018数据结构 链接

• PTA 01-复杂度1 最大子列和问题
  
  
  • 题面
• 思路-1
  
  
  • -TLE-代码
• 思路-2-在线处理
  
  
  • -AC-代码
  • PTA评判结果
• 代码思路

题面

01-复杂度1 最大子列和问题（20 分）
给定K个整数组成的序列{ N1 , N2 , ..., NK }，“连续子列”被定义为{ Ni , Ni+1 , ..., Nj }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：
数据1：与样例等价，测试基本正确性；
数据2：102个随机整数；
数据3：103个随机整数；
数据4：104个随机整数；
数据5：105个随机整数；

输入格式:
输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。
输出格式:
在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

输入样例:
6
-2 11 -4 13 -5 -2
输出样例:
20

作者: DS课程组
单位: 浙江大学
时间限制: 50000ms
内存限制: 64MB

思路-1

首先想到的思路是简单地单纯的暴力枚举，也就是分别枚举起点和终点，这样的话是可以在不计时间的情况下解决问题的，但是提交上去肯定会TLE

---

-TLE-代码

```C++
#include<bits/stdc++.h>

using namespace std;

const int MAX = 200000;
typedef long long LL;

int a[MAX];

int main()
{
LL num;
while(cin >> num)
{
for(LL i = 0; i < num; i++)
{
cin >> a[i];
}
LL MAX = 0;
for(LL i = 0; i < num; i++)
{
for(LL j = i; j < num; j++)
{
LL Temp_Max = 0;
for(LL k = i; k <= j; k++)
{
Temp_Max += a[k];
}
if(Temp_Max > MAX)
MAX = Temp_Max;
}
}
cout<<MAX<<endl;
}
return 0;
}

<pre><code class=" line-numbers"><br />--------------------------

<h1>思路-2-在线处理</h1>

然后就想要缩短时间（废话），一开始想着要一个一个的计算，先算出每一个位之前的最大值，然后后面可以利用，后来觉得还是太啰嗦，就没具体写完，看到了陈越姥姥讲的一种思路，就是在线处理，复杂度O（N），可以一边输入一边处理，这样的话，节约时间，也节约了空间，岂不是美哉

<hr />

<h2><em>-AC-代码</em></h2>

```C++
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int main()
{
LL num = 0;
while(cin >> num)
{
int MAX = 0;
int NOW = 0;
for(LL i = 0; i < num ; i++)
{
int temp = 0;
cin >> temp;
NOW += temp;
if(NOW > MAX)
MAX = NOW;
else if(NOW < 0)
{
NOW = 0;
}
}
cout << MAX <<endl;
}
return 0;
}

---

PTA评判结果

2018/3/17 19:00:35 答案正确 20 01-复杂度1 C++ (clang++) 40 ms
测试点 提示 结果 耗时 内存
0 sample 有正负，负数开头结尾，最大和有更新 答案正确 3 ms 224KB
1 100个随机数 答案正确 2 ms 252KB
2 1000个随机数 答案正确 3 ms 256KB
3 10000个随机数 答案正确 6 ms 256KB
4 100000个随机数 答案正确 40 ms 248KB

就是比暴力美丽的多（/xk）

代码思路

使用动态处理的方法，现将每n个位数的和算出来，和已经保存下来的最大值相比较，如果大于已知的最大值，则更新，否则，由于规定全是负数的话，结果为0，那么每一步都判断一下Temp_Max的正负就好，并不需要担心最大值会丢失，因为如果有最大值，肯定已经保存下来了。