最大连续和|最大连续和 --- 牛客笔试题最大连续和---牛客笔试题

今天在牛客上看到这道题，理解过程中总结了一些经验，在此来分享一下：

文章图片

分析：
(1).这些元素都是负数：这个连续子数组只有一个数，连续最大和是最大的负数；
eg: -1-2-3-4-5连续最大子串：{-1}sum = -1
(2).这些元素都是正数：这个连续子数组是所有元素组成的集合，连续最大和是所有数之和；
eg: 12345连续最大子串{1,2,3,4,5}sum = 1+2+3+4+5
(3).这些元素有正有负：一定是正数在首尾的连续子串，连续最大数就是该子串所有数之和。
eg: 5-23-65连续最大子串{5,-2,3}sum = 5+(-2)+3
其实我们再划分一下，可以(2)划分到(3)中，也是以正数开始以正数结尾的。
【最大连续和|最大连续和 --- 牛客笔试题】所以我们最终划分为这两类：
1.元素全为负数：最大连续子串是只有一个负数组成的子串，这个负数就是元素中最大的那个负数。
2.元素不全为负数：最大连续子串一定是正数在首尾的元素组成的子串。
那么我们写代码时就应该注意，大部分情况都是满足第2种情况的，所以就需要在满足第2种情况的同时注意一下对第1种情况的特殊处理。
先粘上我的代码，再做进一步解释：

#include #include using namespace std; int main() { int n; cin >> n; vector v(n); for (int i = 0; i < n; ++i) { cin >> v[i]; } int sum = 0; int cursum = 0; int max = v[0]; for (int i = 0; i < n; ++i) { cursum += v[i]; if (cursum > sum) sum = cursum; if (cursum < 0) cursum = 0; if (v[i] > max) max = v[i]; } if (max < 0) sum = max; cout << sum; return 0; }

首先先说一下这个特殊处理（元素全为负数的情况），我这里定义了一个max，在遍历这些元素的同时记录下当前元素中最大的数，遍历完成后，如果这些元素中最大的数都是负数，证明所有的元素都是负数，连续最大子串也就是最大的那一个负数组成的集合，连续最大和也就是这个max。
再说一下其他情况的处理，元素不全为负数的情况。这时候我们会发现连续最大子串中至少会有一个正数，而且这个子串的开始和结尾也一定是一个正数。
我们用sum记录最终结果，cursum用来试探相加，下面举个例子理解一下这个过程：（元素不全为负数的情况）
eg：-123-45-68
开始让sum，cursum = 0；
i = 0， cursum= cursum + （-1）= -1；这时我们要是继续从第一位开始算的话，肯定没有从下一位开始计算的和大，因为这已经是个负数了；所以判断如果cursum<0，重新令cursum = 0；也就是说不算这一位了，从下一位开始重新计算；
i = 1，cursum= cursum + （2）= 2；这时cursum>sum，更新sum = cursum。
下面就不再一一叙述下去了，我们可以发现，当cursum<0时，证明前面所组成的子串和已经是负数，所以肯定比正数小，这时我们就可以舍弃前面的，重新开始新的子串相加；当cursum>sum时，证明这时当前遇到的最大的子串和，我们更新sum的值，直到循环结束，sum中得到的就是连续最大和。
最后判断一下元素是不是都为负数，若是，则max就是连续最大和，若不是，sum就是最大连续和。