题解 | #递减种子序列#

递减种子序列

https://www.nowcoder.com/practice/708a3a8603274fc7b5732c5e73617203

知识点:

LIS问题,动态规划

分析:

状态表示:

1.f[i]表示以第i个数字结尾的子序列的最长的递减种子序列

2.属性:max,最长

状态计算:

1.分为两个部分

1.1一个部分是,包含seeds[i]这个数字的,那么以这个结尾的最长的递减子序列长度,抛开这个即将要计算的seeds[i]数字来说,其最长长度为f[j]+1,其中j取的是0~i,表示取一个最长的之前计算的最长递减长度,再加1

1.2另一个部分是不包含seeds[i]的,那么就是以上一个包含了seeds[i]的数字结尾的长度,也就是之前计算的f[i]

综上,f[i] = max(f[i],f[j]+1)

编程语言:

C++

完整代码:

    int f[2510];
    int lengthOfLIS(vector<int>& seeds) {
        int res = 0;
        f[0] = 1;
        for(int i = 0;i<seeds.size();i++){
            f[i] = 1;
            for(int j = 0;j<i;j++){
                if(seeds[i] <seeds[j]){
                    f[i] = max(f[i],f[j] + 1);
                }          
            }
            res = max(res,f[i]);
        }
        return res;
    }

全部评论

相关推荐

深夜书店vv:腾讯是这样的,去年很多走廊都加桌子当工区
点赞 评论 收藏
分享
Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
07-07 14:30
复旦大学 Java
遇到这种人我也不知道说啥了
无能的丈夫:但我觉得这个hr语气没什么问题啊(没有恶意
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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