[Quora] OA求助

在做Quora OA题库的时候,遇到了这道题,不知道怎么做,求大神讲解一下。
maxArithmeticLength
Suppose we have array a and b (no duplicates & sorted)
a = [0,4,8,20]
b = [5,7,12,16,22]

Suppose u can pick any number of element from b (could be 0), and u want to insert them into array a such that all elements in a are increasing by certain number,
so in this example u can pick “12, 16” from b and append into a such that a = [0,4,8,12,16,20], which increase by 4 for each elem‍‍‌‌‌‍‍‍‍‌‍‍‌‍‌‌‌‍‍ent

write a function to return the maximum number of element in a after appending elements from b (in the exmaple above the result is 6), if there is no such case, return -1

中文版:
给2个数组,a, b. 都是本身严格递增的数列。 可以从b里面挑出来元素插入a里面任意位置,使得a可以形成一个递增的等差数列。
a = [3, 5, 9]
b = [1, 7, 11,13]
可以凑成[1,3,5,7,9,11,13]
这个能凑的最长的长度是7, return这个7

试试这个思路?
如果把b全部插入,利用 413 Arithmetic Slices 或者 446 Arithmetic Slices II - Subsequence 找符合条件的Subsequence(必须含有a的element)

1 Like

谢谢老师,我试一下!