牛客711138262号
2022-05-06 14:16 拓竹科技_嵌入式软件
关注
第四题我只写了个n2的动归，过了40，应该可以优化成nlogn，思路是把上升子序列分为两种情况的的dp，一种是断开的上升子序列（也就是有删除一次子数组的），一种是连续的上升子序列
记dp[i][0]代表以下标i的元素为结尾的连续上升子序列
记dp[i][1]代表以下标i的元素为结尾的断开的上升子序列
所有dp[i][0]和dp[i][1]都初始化为1
对于 i - 1
if arr[i] > arr[i-1]: dp[i][0] = dp[i-1][0] + 1
对于 j < i
if arr[i] > arr[j]: dp[i][1] = dp[j][0] + 1
查看原帖
点赞 3
相关推荐
投递淘天集团等公司10个岗位 > 点赞 评论 收藏
分享
11-20 17:40
西安邮电大学 有线传输工程师 点赞 评论 收藏
分享
牛客热帖
正在热议
# 25届秋招总结 #
345488次浏览 3341人参与
# 我的实习求职记录 #
6080365次浏览 83633人参与
# 北方华创开奖 #
39599次浏览 421人参与
# 地方国企笔面经互助 #
4978次浏览 13人参与
# 职场吐槽大会 #
89941次浏览 740人参与
# 选完offer后，你后悔学本专业吗 #
22687次浏览 163人参与
# 百度开奖 #
195416次浏览 1268人参与
# ai智能作图 #
1762次浏览 41人参与
# 运营商笔面经互助 #
92200次浏览 1330人参与
# 实习中的菜狗时刻 #
278388次浏览 2736人参与
# 如果有时光机，你最想去到哪个年纪？ #
23861次浏览 481人参与
# 海康威视求职进展汇总 #
401916次浏览 3414人参与
# 风评不好的公司，你会去吗？ #
20591次浏览 94人参与
# 国企还是互联网，你怎么选？ #
89935次浏览 698人参与
# 软件开发2024笔面经 #
2324630次浏览 48210人参与
# 如何一边实习一边秋招 #
999198次浏览 12693人参与
# 腾讯求职进展汇总 #
197963次浏览 1650人参与
# 银行笔面经互助 #
84502次浏览 893人参与
# 第一份工作应该选择高薪还是大平台 #
88827次浏览 590人参与
# bilibili求职进展汇总 #
33816次浏览 361人参与
# 上班苦还是上学苦呢？ #
79422次浏览 739人参与
# 许愿池 #
215377次浏览 2536人参与