浙江大学数据结构： PAT算法题解分析

01-复杂度1 最大子列和问题（20 分）

假设我们有一个由_K_个整数构成的序列_N₁,N₂,…,NK. 这里的"连续子序列"被定义为从第_i_个元素到第_j_个元素的部分构成的集合{N_i,N{i+1},…,N_j}, 其中满足条件1≤i≤j≤K. 我们将"最大连续子序列和"定义为此类所有可能连续子序列之元素总和中的最大值. 如示例所示：对于序列{-2,11,-4,13,-5,-2}, 其中包含最大值20的一个连续子序列为{11,-4,13}. 现需设计一个程序以计算任意给定整数序列的最大连续子序列和.

本题主要考察不同算法在不同数据环境下运行性能的评估。各组测试数据由以下几部分组成：

• 数据1：等价于样例，并基本达到测试要求；
• 数据2：增加了两个随机整数值；
• 数据3：增加到103个随机整数值；
• 数据4：提升至104个随机整数值；
• 数据5：扩展为105个随机整数值。

输入格式:

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

输出格式:

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

时间复杂度为n的3次方的算法（暴力破解）：

#include

using namespacestd;

int main(){

int