0x01. 前置题目

1. 题目描述

从长度为 \(n\) 的数组中找出一段长度不限的和最大的连续子序列

2. 思路

维护一个 \(sum\) 和 \(maxn\)，逐个遍历元素 \(cur\)，并判断

如果 cur+sum<0，那么 \(sum\) 就替换为 \(cur\)

否则，sum+=cur

每遍历一个元素就 maxn=max(maxn,sum)
这样可以保证我们一定可以找出答案。
另外注意 \(cur\) 可能小于 \(0\)，因此初始时，\(maxn\) 设置为很小的数。

3. 代码

3.1 模拟做法

时间复杂度 \(O(N)\)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    /*下面虽然包含end,但因为是在局部作用域，所以不会命名冲突*/
    
    // 保存答案
    int maxn = -1;  // 设置为比0小的数
    int res_start, res_last;

     // 记录起点和终点    
    int first, end;
    
    int sum = 0;
    // start=-1 表示我们还没找到起点
    // 因为题目的意思是，sum必须>=0
    // 因此我们不能以负数作为起点
    
    int start = -1, last;

    int n;  cin >> n;
    for(int i = 1; i <= n; i ++ )
    {
        int cur;  cin >> cur;
        
        if(i == 1)      first = cur;
        if(i == n)      end = cur;
        
        if(start == -1 && cur < 0)
        {
            // 没确定起点并且当前点不能作为起点,直接跳过
            continue;
        }
        if(sum + cur < 0)
        {
            // cur肯定小于0,因此它不能作为起点
            // 重置sum和start
            sum = 0;
            start = -1;
        }
        else
        {
            if(start == -1) start = cur;
            sum += cur;
            last = cur;
        }
        if(sum > maxn)
        {
            maxn = sum;
            res_start = start;
            res_last = last;
        }
    }
    if(maxn == -1)   
        cout << 0 << ' ' << first << ' ' << end << endl;
    else
        cout << maxn << ' ' << res_start << ' ' << res_last << endl;

    return 0;
}