BensonChen @ 2023-10-04 10:41:31

by AntonyD @ 2023-10-04 10:43:59

这段代码实现了一个动态规划问题，用于找到给定数组中的最长递增子序列（Longest Increasing Subsequence，LIS）的长度。这是一个经典的动态规划问题。

这里有一些关于代码的解释：

1. n 是输入的数组长度。
2. A 是输入的数组。
3. dp 是一个动态规划数组，其中 dp[i] 表示以 A[i] 结尾的最长递增子序列的长度。

然后，代码逐个检查每个元素，并更新 dp[i] 为以 A[i] 结尾的最长递增子序列的长度。

然而，虽然代码的逻辑是正确的，但是在输出最后的结果时，它只输出了以最后一个元素结尾的最长递增子序列的长度，这可能并不是全局的最长递增子序列的长度。

如果你想要找到全局的最长递增子序列的长度，你需要在所有的 dp[i] 中找到最大值，如下所示：

#include <bits/stdc++.h>

using namespace std;

int n, A[5140], dp[5140];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }
    int max_len = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++) {
            if (A[j] < A[i] && dp[i] < dp[j] + 1) dp[i] = dp[j] + 1;
        }
        max_len = max(max_len, dp[i]);
    }
    cout << max_len;
    return 0;
}

这样，max_len 就会存储全局的最长递增子序列的长度，而不仅仅是以最后一个元素结尾的最长递增子序列的长度。

by LDY113 @ 2023-10-04 10:44:04

看看题解

读入数据；

大循环开始，从 11 到 nn，计算 fifi​，记得初始值是 11；

小循环，从 11 到 i−1i−1，如果 ajaj​ 小于 aiai​ 的话，说明这个数可以和 fifi​ 组成上升子序列，则 fifi​ 取 max⁡(fi,fj+1)max(fi​,fj​+1)；

寻找最大值；

by AntonyD @ 2023-10-04 10:44:42

PS:你的代码格式有错，记得改一下

by BensonChen @ 2023-10-04 10:49:58

#include <bits/stdc++.h>

using namespace std;

int n,A[5140],dp[5140];

int maxn=-1e9;
int main(){
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>A[i];
    }
    for (int i=1;i<=n;i++){
        dp[i]=1;
        for (int j=1;j<=i;j++){
            if(A[j]<A[i]&&dp[i]<dp[j]+1)dp[i]=dp[j]+1;
        }
        if(dp[i]>maxn)maxn=dp[i];
    }
    cout<<maxn;
    return 0;
}

AC了

by Youngkx @ 2023-10-09 21:50:42

AC代码：

#include <iostream>
using namespace std;
int dp[5100], a[5100], n;
int maxn;
int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i){
        dp[i] = 1;
        for(int j = 1; j < i; ++j) if(a[j] < a[i]) dp[i] = max(dp[j] + 1, dp[i]);
        maxn = max(maxn, dp[i]);
    }
    cout << maxn;
    return 0;
}

注意在第二层for循环中可能出现原数据忽上忽下的情况，需要每次判一遍最长大小。

然后就是要有一个数据记录一下每次最大个数的值，因为dp[i]数组每次会变化。