本文共 1493 字，大约阅读时间需要 4 分钟。

最大子列和问题之前便有所耳闻，也有所尝试，但皆以失败而不了了之。今日查阅资料，从其他博主那里学习到了两种不错的最大子列和解法，发在博客中以作学习记录。

题目描述

给定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：与样例等价，测试基本正确性；

6-2 11 -4 13 -5 -2

输出样例：

20

解法一：时间复杂度O(n ^ 2)

二次方的时间复杂度便可知道这是一个运用双重循环的解题思路，幸亏此题的限定时间给出的范围很大，n方的时间复杂度并没有超时，以下为代码：

#include 
   
    using namespace std;typedef long long ll;const ll maxn = 100005;ll num[maxn] = {   0};ll s1(ll n){    ll maxSum=0; for(ll i=0;i
    
     >k; for(ll i=0;i
     
      >num[i]; } cout<
     
    
   

代码很直观也很暴力，此处不做赘述。

解法二：时间复杂度O(n)

此种解法直接将时间复杂度降为一阶，是我比较推崇的解法，感谢博主大犇！

#include 
   
    using namespace std;typedef long long ll;const ll maxn = 100005;ll num[maxn] = {   0};ll s2(ll n){    ll maxSum,tmpSum; maxSum=tmpSum=0; for(ll i=0;i
    
     >k; for(ll i=0;i
     
      >num[i]; } cout<
     
    
   

算法核心：

ll s2(ll n){    ll maxSum,tmpSum; maxSum=tmpSum=0; for(ll i=0;i

其中的tmpSum和maxSum的动态变化为关键。

tmpSum += num[i];  if(tmpSum<0){      tmpSum = 0;  }

临时的tmpSum（我认为将它称作“暂时充当中间值的”更为贴切）每次都加上数组中的一个值，而当这个“临时的”总和小于0时，它对接下来的最大子序列没有任何帮助（因为加上一个负数，总和一定减少），因此归零（即为上述代码的if条件句区块）。

最大子列和问题使用分治的递归思想也可解，但时间复杂度步入Solution2完美（分治的时间复杂度为O(n * logn），因此博主没有学习分治之解法，有兴趣的读者可自行搜索查看。