原命题:中国大学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的正负就好,并不需要担心最大值会丢失,因为如果有最大值,肯定已经保存下来了。

标签: PTA

添加新评论