c++洛谷p2678

洛谷P2678是一道关于C++编程的题目，主要考察的是动态规划（Dynamic Programming, DP）中的最长上升子序列（Longest Increasing Subsequence, LIS）问题。以下是这道题目的详细介绍和解题思路：

### 题目描述
给定一个长度为n的整数序列，求出其中最长的上升子序列的长度。最长上升子序列是指序列中的一个子序列，该子序列中的每一个元素都比前一个元素大。

### 输入格式
第一行包含一个整数n，表示序列的长度。
第二行包含n个整数，表示序列中的元素。

### 输出格式
输出一个整数，表示最长上升子序列的长度。

### 样例输入

5
1 2 3 2 5

### 样例输出

4

### 解题思路
1. **动态规划**：我们可以用一个数组`dp`来记录以每个元素结尾的最长上升子序列的长度。初始时，`dp[i] = 1`，因为每个元素本身就是一个长度为1的上升子序列。
2. **状态转移方程**：对于每个元素`arr[i]`，我们遍历其前面的所有元素`arr[j]`，如果`arr[j] < arr[i]`，则更新`dp[i] = max(dp[i], dp[j] + 1)`。
3. **最终答案**：遍历`dp`数组，找到其中的最大值，即为最长上升子序列的长度。

### 代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

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

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, dp[i]);
    }

    cout << ans << endl;
    return 0;
}

### 解释
1. **输入处理**：首先读取序列的长度n和序列中的元素。
2. **动态规划数组初始化**：初始化`dp`数组，所有元素初始值为1。
3. **状态转移**：对于每个元素，更新`dp[i]`为`max(dp[i], dp[j] + 1)`，其中`arr[j] < arr[i]`。
4. **结果输出**：遍历`dp`数组，找到最大值作为最终答案。