美团最后一道编程题
题目描述比较简洁： 给一个数组长度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，i从0到n遍历作为“好序列”的末尾，然后j从0到i遍历作为上一个状态：f[i] = 某函数(f[j])，试图找到状态转移方程，实际上，只要arr[i]==arr[j-1]，那么“好序列”的长度就有机会在以j结尾的“好序列”的基础上+1，所以f[i] = max(f[i],f[j]+1)，在if arr[i]==arr[j-1]的条件下成立。
代码：（不知道对不对哈）
#好序列
n = int(input().strip())
arr = list(map(int,input().strip().split()))
dp = [0]*n
for i in range(n):
for j in range(i):
if j>=1 and arr[j-1]==arr[i]:
dp[i] = max(dp[i],dp[j]+1)
res = max(dp)+2
if res<3:print(0)
else:print(res)
# print(dp)
#晒一晒我的offer##你收到了团子的OC了吗##美团笔试#
查看23道真题和解析