题解 | #最长上升子序列(一)#
最长上升子序列(一)
https://www.nowcoder.com/practice/5f65ccbb025240bd8458eb6479c2612e
本人小白,正在练习动态规划,但是我不知道这样写是不是动态规划,希望大佬看过后告知 #include <stdio.h> #include <stdlib.h> int main() { int n; scanf("%d", &n); int* arr = (int*)malloc(sizeof(int) * n); for (int i = 0; i < n; i++) { scanf("%d", arr + i); } int* dp = (int*)malloc(sizeof(int) * n); for (int l = 0; l < n; l++) { dp[l] = 1; } for (int i = 1; i < n; i++) { int smax = 0; for (int j = i - 1; j >= 0; j--) { if (arr[i] > arr[j]) { if (dp[j] > smax) smax = dp[j]; } } dp[i] = smax + 1; } int Max = 0; for (int k = 0; k < n; k++) { if (dp[k] > Max) Max = dp[k]; } printf("%d", Max); return 0; }