题解 | 拦截导弹

#include <stdio.h>
#include <stdlib.h>

int longestIncreasingSubsequence(int arr[], int n) {
    if (n == 0) return 0;

    int *dp = (int*)malloc(n * sizeof(int)); // dp[i] 表示以 arr[i] 结尾的 LIS 长度
    int max_len = 1; // 全局最长长度

    for (int i = 0; i < n; i++) {
        dp[i] = 1; // 初始化为1（每个元素自身）
        for (int j = 0; j < i; j++) {
            if (arr[j] >= arr[i] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1; // 更新更长的子序列
            }
        }	
        if (dp[i] > max_len) max_len = dp[i]; // 更新全局最大值
    }

    free(dp);
    return max_len;
}

int main() {
	int n;
	int arr[27];
	scanf("%d",&n);
	for(int i = 0 ; i < n ; i++){
		scanf("%d",&arr[i]);
	}
    

    printf("%d\n", longestIncreasingSubsequence(arr, n));
    return 0;
}