最长递增(减)子序列

拦截导弹

http://www.nowcoder.com/questionTerminal/dad3aa23d74b4aaea0749042bba2358a

// runtime: 4ms
// space: 504K
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX = 25;

int arr[MAX];
int dp[MAX]; // dp[i]定义为:以arr[i]为结尾的最长递增(减)子序列。

int MaxDecSubsequence(int k) {
    int answer = 0;
    for (int i = 0; i < k; ++i) {
        dp[i] = 1;

        for (int j = 0; j < i; ++j) {
            if (arr[i] <= arr[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        answer = max(answer, dp[i]);
    }
    return answer;
}

int main() {
    int k;
    while (scanf("%d", &k) != EOF) {
        for (int i = 0; i < k; ++i) {
            scanf("%d", &arr[i]);
        }

        printf("%d\n", MaxDecSubsequence(k));
    }
    return 0;
}

很经典的dp问题。

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 11:24
大家还是用ai改吧,我心疼得要死,就当花钱买教训吧,人家直接拿完钱就跑路了
程序员小白条:简历修改700....神奇,又不是帮你面试,咋的,简历修改从双非变92了还是没实习变成有大厂实习了
点赞 评论 收藏
分享
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 11:20
点赞 评论 收藏
分享
评论
3
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务