Agoda bankok 店面挂经

店面有两道题：
第一道是给你一个key， value， timestamp的tuple的array，给你一个key， timestamp返回value。
第二道题是longest bitnoic subsequence, 这道题比较坑的是和面试官确认是不是一定要有increasing part + decreasing part才算bitonic，例如一个
array[1,2,3,4,5]和[5,4,3,2,1] 都不算， [1,2,5,4,3]这种才行。

1. def longest_bitonic_arr(arr):
   
2.     n = len(arr)
   
3.     increasing_dp = [1] * n
   
4.     bitonic_dp = [0] * n
   
5. 
   
6.     for i in range(n):
   
7.         for j in range(i):
   
8.             if arr[j] < arr[i]:
   
9.                 increasing_dp[i] = max(increasing_dp[i], increasing_dp[j] + 1)
   
10.             elif arr[i] < arr[j]:
    
11.                 bitonic_dp[i] = max(bitonic_dp[j] + 1, increasing_dp[j] + 1, bitonic_dp[i])
    
12.             else:
    
13.                 bitonic_dp[i] = max(bitonic_dp[j], increasing_dp[j], bitonic_dp[i])
    
14. 
    
15.     return max(max(bitonic_dp), max(increasing_dp))

复制代码

我用dp做的不知道为啥hackerank跑不过。
面试完后我查资料才知道bitonic是允许单调的，单调递增和单调递减的array也都是合规的

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

//www.geeksforgeeks.org/longest-bitonic-subsequence-dp-15/

已经面挂好几家了都开没信心了诶，
求大米

楼主准备去曼谷吗哈哈？