数据结构学习（PTA）——最大子序列问题

问题描述

给定K个整数组成的序列{ N 1 , N 2 , . . . , N k N_1, N_2, ..., N_k N1​,N2​,...,Nk​}, 连续子列被定义为{ N i , N i + 1 , . . . , N j N_i, N_{i+1}, ..., N_j Ni​,Ni+1​,...,Nj​}，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

• 数据1：与样例等价，测试基本正确性；
• 数据2： 1 0 2 10^2 102个随机整数；
• 数据3： 1 0 3 10^3 103个随机整数；
• 数据4： 1 0 4 10^4 104个随机整数；
• 数据5： 1 0 5 10^5 105个随机整数；

输入格式：

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

输出格式：

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

输入样例：

6
-2 11 -4 13 -5 -2

输出样例

20

题目分析

第一个想法：简单粗暴的对给出的数组进行分块，第一次每一块一个元素，第二次两个元素…第N次N个元素，再分别计算每一块的最大值，选出最大的那一个。

#include
using namespace std;
int main() {int n, i, j, k, a[100000]; // ijk为循环变量int max = 0; //最终结果int mid = 0; //中间变量cin >> n;for (i = 0; i < n; i++) {cin >> a[i];}for (j = 1; j <= n; j++) {for (k = 0; k < n - j + 1; k++) {mid = 0;for (i = k; i < j; i++) {mid += a[i];}if (mid > max) {max = mid;}}}cout << max;return 0;
}

但是这样由于运用到了三重循环，时间复杂度为 O n 3 O_{n^3} On3​，会超时。

于是对方法进行了更新，采用两重循环。代码如下：

#include
using namespace std;
int main() {int n, i, j, k, a[100000];int max = 0;cin >> n;for (i = 0; i < n; i++) {cin >> a[i];}for (i = 0; i < n; i++) {int mid = 0;for (j = i; j < n; j++) {mid += a[j];if (mid > max) {max = mid;}}}if (max < 0) {max = 0;}cout << max;return 0;
}

这样时间复杂度为 O n 2 O_{n^2} On2​,可以AC。

对比两段代码，第一段代码是从分段1~N依次计算。而第二段代码是抛出元素，第一次为以a[0]首元素的段，第二次以a[1]为首元素依次进行，这样可以省略一重循环。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！