输入n个各不相同的数,求其最长上升子序列,例如n = 6,3 2 6 1 4 5,其最长上升子序列为1 4 5长度为3
#include<iostream> using namespace std; #include<vector> int a[1005]; int dp[1005]; int main() { int n; cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; } //暴力搜 int ans = -1; for (int i = 1; i <= n; ++i) { int t = a[i]; int sum = 1; for (int j = 1; j <= n; ++j) { if (a[j] > t) { sum++; t = a[j]; } } if (sum > ans) { ans = sum; } } cout << ans << endl; int ans1 = 0; /* 所谓动态规划,就是把每个点的状态都记录在表内,如序列3 2 6 1 4 5下标从1开始,dp[1] =1,dp[2] = 1,dp[3] = dp[1]+1/dp[2]+1都等于2 ,说明三个前三个数右两条不相同长度为2的升序序列 */ for (int i = 1; i <= n; ++i) { //遍历每个点的状态 dp[i] = 1; //初始状态为1 for (int j = 1; j < i; ++j) { //判断,若符合条件,依次与前面的状态相加 if (a[j] < a[i]) { dp[i] = max(dp[i], dp[j] + 1); //取此轮最优状态 } } ans1 = max(dp[i], ans1); //取当前最优状态 } cout << ans1 << endl; //输出结果 system("pause"); return 0; }