PTA（顺序表）2-3 最长连续递增子序列

2-3 最长连续递增子序列

分数 6

作者 DS课程组

单位 浙江大学

给定一个顺序存储的线性表，请设计一个算法查找该线性表中最长的连续递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。

输入格式:

输入第1行给出正整数n（≤105）；第2行给出n个整数，其间以空格分隔。

输出格式:

在一行中输出第一次出现的最长连续递增子序列，数字之间用空格分隔，序列结尾不能有多余空格。

输入样例：

1
2
15
1 9 2 5 7 3 4 6 8 0 11 15 17 17 10

输出样例：

1
3 4 6 8

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
using namespace std;

// 定义顺序表结构：存储数据的数组和表长
typedef struct {
    int *data;
    int length;
} sqList;

// 初始化顺序表
void initList(sqList &L, int n) {
    L.data = new int[n];
    L.length = 0;
}

int main() {
    int n;
    cin >> n;
    sqList L;
    initList(L, n);
    // 将读取的n个整数存入顺序表L
    for (int i = 0; i < n; ++i) {
        cin >> L.data[i];
        L.length++;
    }

    // 查找线性表中最长的连续递增子序列
    int best_start = 0;
    int best_end = 0;
    int start = 0;
    int max_length = 1;
    int current_length = 1;
    for (int i = 0; i < n-1; ++i) {
        if (L.data[i] < L.data[i+1]) {
            current_length++;
        } else { // 重新开始
            start = i+1;
            current_length = 1;
        }
        if (current_length > max_length) { // 更新最大长度
            max_length = current_length;
            best_start = start; // 更新最长的起始下标
            best_end = i+1; // 更新最长的终点下标
        }
    }

    // 输出最长连续递增子序列
    for (int j = best_start; j <= best_end; j++) {
        if (j != best_start) {
            cout << " ";
        }
        cout << L.data[j];
    }
}

Summary

“线性遍历 + 状态实时记录” 的思路查找最长连续递增子序列，核心逻辑符合问题需求，且时间复杂度为 O (n)（仅遍历一次序列），是高效的解决方案，具体可拆解为 3 步：

  1. 状态初始化：用start记录当前递增子序列的起始下标，current_length记录当前子序列长度（初始为 1，因单个元素也是子序列）；用best_start/best_end记录最长子序列的起止下标，max_length记录其长度。

  2. 线性遍历判断

    ：遍历序列时，对比当前元素与下一个元素：

    • 若递增（L.data[i] < L.data[i+1]），则当前子序列长度current_length加 1；
    • 若不递增，重置start为下一个元素下标，current_length重新记为 1（开启新的子序列统计）。

  3. 实时更新最长子序列：每次遍历后，若当前子序列长度超过max_length，则更新max_length及最长子序列的起止下标，确保始终记录当前找到的最长子序列。

之前错误点

  • 错误点：max_length初始值设为 0，不符合 “子序列最小长度为 1” 的客观事实（即使序列只有 1 个元素，子序列长度也为 1）。