域名是否就是网站,在线阅读小说网站怎么建设,网站注册域名多少钱,建设免费网站制作我参考的B站up的思路
题目
题目链接 给定K个整数组成的序列{ N 1 , N 2 , …, N K }#xff0c;“连续子列”被定义为{ N i , N i1 , …, N j }#xff0c;其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 1…我参考的B站up的思路
题目
题目链接 给定K个整数组成的序列{ N 1 , N 2 , …, N K }“连续子列”被定义为{ N i , N i1 , …, N j }其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序计算给定整数序列的最大子列和。
本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下
数据1与样例等价测试基本正确性 数据2102个随机整数 数据3103个随机整数 数据4104个随机整数 数据5105个随机整数 输入格式: 输入第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 的大小来记录全局最大的子列和在给定的问题情境下这样的贪心策略确实能够保证找到整个序列的最大子列和实现了从局部最优逐步走向全局最优的目标符合贪心算法的基本思路。 总体而言无论是从动态规划角度的状态定义、状态转移和最优子结构体现还是从贪心算法角度的局部最优决策来达成全局最优的思路来看这道题考查的算法知识都落在这两种常见算法思想的范围里。
源码
源码
