题解 | #最长上升子序列(一)#

使用动态规划来解决这个问题。定义一个数组dp，其中dp[i]表示以第i个元素结尾的最长严格上升子序列的长度。

初始化dp数组的所有元素为1，因为每个元素本身都可以作为一个长度为1的上升子序列。

接下来，可以按照以下步骤来计算dp数组的值：

#1.遍历数组arr，对于每个元素arr[i]，将dp[i]初始化为1

#2.再次遍历数组arr，对于每个元素arr[i]，从arr[0]到arr[i-1]逐个比较，如果arr[i]大于arr[j]，则更新dp[i]为dp[j]+1的较大值（如果dp[j]+1大于当前的dp[i]）。

#3.在遍历过程中，通过比较dp[i]和当前最长严格上升子序列的长度，可以实时更新最长子序列的长度。

最终，最长严格上升子序列的长度就是dp数组中的最大值。

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

int longest(vector<int>& arr) {
    int n = arr.size();
    vector<int> dp(n, 1);

    int maxLength = 1;

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

    return maxLength;
}

int main() {
    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++)   
    cin >> arr[i];
    int maxLength = longest(arr);
    cout<< maxLength << endl;

    return 0;
}