浙大版《数据结构（第2版）》题目集最长连续递增子序列 (20分)

一、解题思路

采用双指针法，就像切割字符串一样，来处理这个序列。
首先定义一对前后指针left和right，分别表示本递增区间的起始位置和终止位置
然后定义一个slnStart，来确定当前最优解（当前找到的最长递增序列）的起始位置
定义一个maxLength，其含义为当前找到的最长长度，设置初始值为1，意思是即使向量全逆序，也至少要输出一个元素
然后呢，挨个扫描向量的元素，查看下一个元素是不是递增的，直到找到本递增区间的终止位置
然后，根据得到的left和right值，就可以确定这个递增区间的长度，位right - left + 1，即使向量为全逆序，那么这个值也为1
根据当前找到的这个递增区间的长度和找到的最优解的长度maxLength比对，如果当前找到的这个递增区间的长度right - left + 1更长，就要更新maxLength和slnStart
然后输出即可

二、性能分析

只遍历了向量一次，所以时间复杂度为$O(n)$O(n)
同时只设置了固定个变量，所以空间复杂度为$S(1)$S(1)

三、解题代码

#include <iostream>
#include <vector>
using namespace std;
void sln(const vector<int>& vec){
    auto len = vec.size();
    auto left = 0;
    auto right = 0;
    int cur;
    int maxLength = 1;
    int slnStart = 0;
    for(; left < len; left++){
        cur = vec[left];
        for(right = left; right + 1 < len && vec[right + 1] > cur; right++){
            cur = vec[right + 1];
        }
        if(right - left + 1 > maxLength){
            maxLength = right - left + 1;
            slnStart = left;
        }
        left = right;        
    }
    for(int i = slnStart; i < slnStart + maxLength - 1; i++)
        cout << vec[i] << ' ';
    cout << vec.at(slnStart + maxLength - 1) << endl;    
}
int main(){
    int n;
    cin >> n;
    vector<int> vec(n, 0);
    for(int i = 0; i < n; i++)
        cin >> vec[i];
    sln(vec);
    return 0;
}

四、运行结果