1226: 求和游戏
Time Limit: 1 SecMemory Limit: 12 MB
Submit: 345Solved: 94
Description
小明有n个球排成一行，每个球上有个数字。现在小明选择两个球，使这两个球之间的数字和最大（包括这两个球）。如果这个最大的和不为正，则输出“Game Over”。
Input
第一行输入T，有T组数据。
每组数据：输入n（1<n<1000000 ），再输入n个整数，表示第1个球到第n个球上的数字，每个球上的数字大于-100，小于100。
Output
对于每组数据，输出最大和或者”Game Over“，占一行。
Sample Input
6
5
3 -5 7 -2 8
3
-1 2 3
4
-1 1 -111 1111
3
-1 -2 -3
3
1 -1 0
6
100 -1 -1 -1 -1 -1 -1
Sample Output
13
5
1001
Game Over
Game Over
99
入门：最大子序列：leetcode-最大子序和(四种) - zwz的学习之路 - CSDN博客
这个博客给了三种方法：
1，暴力枚举O(n^3)（易超时）
2，改进暴力O(n^2)：每次我们都是重复计算了一部分子序列，即当我计算前两个时，第三次我还是会计算前两个在加第三个，这样就造成了O(N^3)，现在我们根据前一次的进行计算，那么将会减少一层循环.
3，扫描法O（n）：当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和。
据说这道题是《编程珠机》里面的题目，叫做扫描法，速度最快，扫描一次就求出结果，复杂度是O（n）。书中说，这个算法是一个统计学家提出的。 这个算法如此精炼简单，而且复杂度只有线性。但是我想，能想出来却非常困难，而且证明也不简单。在这里，我斗胆写出自己证明的想法： 关于这道题的证明，我的思路是去证明这样的扫描法包含了所有n^2种情况，即所有未显示列出的子数组都可以在本题的扫描过程中被抛弃。 1 首先，假设算法扫描到某个地方时，始终未出现加和小于等于0的情况。 我们可以把所有子数组（实际上为当前扫描过的元素所组成的子数组）列为三种： 1.1 以开头元素为开头，结尾为任一的子数组 1.2 以结尾元素为结尾，开头为任一的子数组 1.3 开头和结尾都不等于当前开头结尾的所有子数组 1.1由于遍历过程中已经扫描，所以算法已经考虑了。1.2确实没考虑，但我们随便找到1.2中的某一个数组，可知，从开头元素到这个1.2中的数组的加和大于0（因为如果小于0就说明扫描过程中遇到小于0的情况，不包括在大前提1之内），那么这个和一定小于从开头到这个1.2数组结尾的和。故此种情况可舍弃 1.3 可以以1.2同样的方法证明，因为我们的结尾已经列举了所有的情况，那么每一种情况和1.2是相同的，故也可以舍弃。 2 如果当前加和出现小于等于0的情况，且是第一次出现，可知前面所有的情况加和都不为0 一个很直观的结论是，如果子段和小于0，我们可以抛弃，但问题是是不是他的所有以此子段结尾为结尾而开头任意的子段也需要抛弃呢？ 答案是肯定的。因为以此子段开头为开头而结尾任意的子段加和都大于0（情况2的前提），所以这些子段的和是小于当前子段的，也就是小于0的，对于后面也是需要抛弃的。也就是说，所有以之前的所有元素为开头而以当前结尾之后元素为结尾的数组都可以抛弃了。 而对于后面抛弃后的数组，则可以同样递归地用1 2两个大情况进行分析，于是得证。 --------------------- 作者：zwzsdy 来源：CSDN 原文：leetcode-最大子序和(四种) - zwz的学习之路 - CSDN博客 版权声明：本文为博主原创文章，转载请附上博文链接！
4.动态规划法
设sum[i]为以第i个元素结尾且和最大的连续子数组。假设对于元素i，所有以它前面的元素结尾的子数组的长度都已经求得，那么以第i个元素结尾且和最大的连续子数组实际上，要么是以第i-1个元素结尾且和最大的连续子数组加上这个元素，要么是只包含第i个元素，即sum[i] = max(sum[i-1] + a[i], a[i])。可以通过判断sum[i-1] + a[i]是否大于a[i]来做选择，而这实际上等价于判断sum[i-1]是否大于0。由于每次运算只需要前一次的结果，因此并不需要像普通的动态规划那样保留之前所有的计算结果，只需要保留上一次的即可，因此算法的时间和空间复杂度都很小 ！
本题是属于有条件的最大子序列之和，因为个数必须大于等于2
附上大佬的代码：
网友评论