使用C++语言完成文件里的最长单调递增子序列问题

要使用C++语言完成“最长单调递增子序列”问题，可以遵循以下步骤：

### 1. 理解问题
目标是找到一个序列中最长的单调递增子序列。例如，对于序列 `{97, 1, 37, 97, 84, 34, 81, 3, 20, 32, 2, 99, 4, 89, 99, 72, 59, 31, 21, 70}`，其中一个最长单调递增子序列是 `{1, 37, 81, 89, 99}`。

### 2. 设计算法
我们可以使用动态规划来解决这个问题。定义 `dp[i]` 表示以第 `i` 个元素结尾的最长单调递增子序列的长度。

### 3. 实现代码
以下是完整的C++代码实现：

#include <iostream>
#include <vector>
using namespace std;

void printLIS(vector<int>& arr, vector<int>& dp, vector<int>& predecessor) {
    int max_length = 0;
    int max_index = -1;
    
    for (int i = 0; i < dp.size(); ++i) {
        if (dp[i] > max_length) {
            max_length = dp[i];
            max_index = i;
        }
    }

    cout << "The longest increasing subsequence is: ";
    vector<int> lis;
    while (max_index != -1) {
        lis.push_back(arr[max_index]);
        max_index = predecessor[max_index];
    }
    for (auto it = lis.rbegin(); it != lis.rend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {97, 1, 37, 97, 84, 34, 81, 3, 20, 32, 2, 99, 4, 89, 99, 72, 59, 31, 21, 70};
    int n = arr.size();
    vector<int> dp(n, 1); // 初始化dp数组，所有位置初始值为1
    vector<int> predecessor(n, -1); // 记录前驱节点

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                predecessor[i] = j;
            }
        }
    }

    printLIS(arr, dp, predecessor);

    return 0;
}

### 4. 代码解释
- **初始化**：
- `dp` 数组用于存储以每个元素结尾的最长单调递增子序列的长度，初始值为1（因为每个元素本身可以作为一个长度为1的子序列）。
- `predecessor` 数组用于记录每个元素在最长单调递增子序列中的前驱节点，初始值为-1。

- **动态规划**：
- 外层循环遍历每个元素 `i`。
- 内层循环遍历所有在 `i` 之前的元素 `j`。
- 如果 `arr[i]` 大于 `arr[j]` 并且 `dp[i]` 小于 `dp[j] + 1`，则更新 `dp[i]` 和 `predecessor[i]`。

- **打印结果**：
- 找到 `dp` 数组中的最大值及其对应的索引。
- 使用 `predecessor` 数组回溯得到最长单调递增子序列，并按顺序打印。

### 5. 运行代码
将上述代码保存为一个 `.cpp` 文件，然后使用C++编译器进行编译和运行。例如，在命令行中执行以下命令：

g++ -o lis longest_monotone_subsequence.cpp
./lis

运行后，程序将输出最长单调递增子序列。