PTA数据结构编程题7-1最大子列和问题

我参考的B站up的思路

题目

题目链接
给定K个整数组成的序列{ N
1
​
, N
2
​
, …, N
K
​
}，“连续子列”被定义为{ N
i
​
, N
i+1
​
, …, N
j
​
}，其中 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

题目分析

由题目给出的数据范围，我们可以创建一个大小为10^5的数组来储存数据。
然后我们思考如何得出答案。答案要求最大的子列和，那么我们就想到给数组中的元素做加法，那么这个加法什么时候做到题目要求的连续元素组成且最大呢？
我们可以把每次累加的结果存起来，一但这个累加的结果为负数。说明它对于后续子列和的计算效果都是使子列和变小的。那么怎么办？
我们可以把它给归0,重新从这步出发，再算子列和。
同时，我们要定义一个变量为max，初始化为数组第一个元素的值，一旦子列和大于max，我们就更新max的值，当sum走到负数的结果，也就意味着它不会再超越max了，只有把它归0,重新再算才有可能找到新的最大子列和。

代码如下

考察到的算法知识：

道题考察的算法知识属于动态规划（也常被称为动态规划思想的简单应用）以及贪心算法的范畴，以下是具体分析：
动态规划角度
状态定义：
这里用变量 sum 来记录以当前元素结尾的连续子列的和，它可以看作是一种状态表示。例如在遍历序列的过程中，每到一个新元素，sum 的值会根据前一个位置的状态（也就是前一个元素结尾的连续子列和情况）以及当前元素的值来更新，符合动态规划通过定义状态来描述问题中间结果的特点。
状态转移：
核心代码 sum += ret[i]; if (sum < 0) { sum = 0; } 体现了状态转移的过程。当把当前元素 ret[i] 加入到前面的子列和 sum 中后，如果 sum 变成负数了，就意味着从开头到当前位置的这个连续子列已经没有继续扩展下去对求最大子列和有帮助了（因为它只会让后续的和变小），所以将 sum 置为 0，相当于重新从当前位置开始寻找新的可能构成最大子列和的连续子列，这种根据之前的状态以及当前情况来更新状态的方式就是典型的动态规划中的状态转移思路。
最优子结构性质：
整个序列的最大子列和问题可以分解为求以每个位置结尾的连续子列中的最大子列和，然后再从这些局部的最大子列和中找出全局最大的那个。以某个位置结尾的最大子列和的求解依赖于前面位置的相关信息（也就是前面位置结尾的连续子列和等情况），体现了最优子结构性质，即一个最优解可以由子问题的最优解组合而成，这也是动态规划所依据的重要性质之一。
贪心算法角度
局部最优决策：
在代码中，每当 sum 小于 0 时，就舍弃之前积累的子列（将 sum 置 0），这相当于做出了一个贪心的选择，即只关注当前能获得的最大利益（让子列和尽可能大），不考虑之前已经走过但对后续求和不利的那些元素构成的子列了，每次都选择当前看起来最优的策略（保证子列和非负，以期后面能得到更大的总和），希望通过这样一步步的局部最优决策，最终达到全局最优解（找到最大子列和）。
最终达到全局最优：
通过不断地按照这样的贪心策略去更新 sum 并比较 sum 和 max 的大小来记录全局最大的子列和，在给定的问题情境下，这样的贪心策略确实能够保证找到整个序列的最大子列和，实现了从局部最优逐步走向全局最优的目标，符合贪心算法的基本思路。
总体而言，无论是从动态规划角度的状态定义、状态转移和最优子结构体现，还是从贪心算法角度的局部最优决策来达成全局最优的思路来看，这道题考查的算法知识都落在这两种常见算法思想的范围里。

源码

源码