美团923笔试最后一道编程题咋写
题目描述比较简洁:
给一个数组长度n
给一个长度为n的数组
如果这个数组满足“a[i] = a[i-2]”对于任意i成立,就是“好序列”
问最长的子“好序列”多长,你可以任意删除元素
样例:
input:
①
4
[1,2,1,2]
output:
4
②
input:
4
[1,1,1,1]
output:
4
我也搞不太明白这个“序列”,他应该说的是数组吧?
给一个数组长度n
给一个长度为n的数组
如果这个数组满足“a[i] = a[i-2]”对于任意i成立,就是“好序列”
问最长的子“好序列”多长,你可以任意删除元素
样例:
input:
①
4
[1,2,1,2]
output:
4
②
input:
4
[1,1,1,1]
output:
4
我也搞不太明白这个“序列”,他应该说的是数组吧?
全部评论
蹲一下,开始想二维dp但是没弄出来,后面暴力回溯过了10%超时了![](https://uploadfiles.nowcoder.com/images/20220815/318889480_1660553763930/8B36D115CE5468E380708713273FEF43)
这不是倒数第二道吗(
类比最长上升子序列和最长等差子序列,dp[i][j]表示截止到i,以a[i]结尾上一个数为j的好序列的长度。二重for就OK。
第一题怎么做啊。。
这题ai范围小于1000,肯定要考虑这一点的
相关推荐
点赞 评论 收藏
分享
![](https://static.nowcoder.com/head/2photo.jpg)
点赞 评论 收藏
分享
01-14 20:42
南昌航空大学科技学院 前端工程师 点赞 评论 收藏
分享
![](https://static.nowcoder.com/fe/file/oss/1716965564844UEBJN.png)
![](https://static.nowcoder.com/fe/file/oss/1716965585666UBBME.png)
腾讯
| 校招
| 超多精选岗位
点赞 评论 收藏
分享