B3637 最长上升子序列 - 洛谷

代码区：

#include<bits/stdc++.h>using namespace std;int main(){int n;cin >> n;int arry[n],dp[n];for(int i=0;i<n;i++){cin >>arry[i];dp[i]=1;}/*在 i 之前可能存在多个 j 满足 arry[j] < arry[i]，我们需要找出能让以 i 结尾的上升子序列长度最长的那个 j。所以不能简单地把 dp[i] 更新为 dp[j] + 1，而是要取 dp[j] + 1 和当前 dp[i] 中的较大值，即 dp[i] = max(dp[j] + 1, dp[i])。这样就能保证 dp[i] 始终记录的是以第 i 个元素结尾的最长上升子序列的长度。*/for(int i=0;i<n;i++){for(int j=0;j<i;j++){if(arry[j]<arry[i]){dp[i]=max(dp[j]+1,dp[i]);}}}sort(dp,dp+n);cout << dp[n-1];return 0;
}

欢迎各位读者提出意见。

（菜菜洛谷奋斗小日记）