给定一个排序的数字列表,我想找到最长的子序列,其中连续元素之间的差异在几何上增加.所以,如果列表是
1, 2, 3, 4, 7, 15, 27, 30, 31, 81
那么子序列就是1, 3, 7, 15, 31.或者考虑1, 2, 5, 6, 11, 15, 23, 41, 47哪个具有5, 11, 23, 47a = 3且k = 2的子序列.
这可以在O(n 2)时间内解决吗？其中n是列表的长度.
我感兴趣的是差异的进展是ak,ak 2,ak 3等的一般情况,其中a和k都是整数,并且在a = 1 的特殊情况下,差异的进展是k,k 2,k 3等