拼多多编程第四题求思路

昨天考完问了一个大神，把整个数组延长，0到n-1再到2n-1(这样只要O(n)空间复杂度就能得到距离)， 然后因为要求的值是A[i]+A[j]+j-i，转化一下就是A[j]+j + A[i] - i。之后好像是用RMQ算法O(nlogn)时间复杂度可以出来。具体我也还没太想明白

求题目描述！！

果然是dp😣所以就没做，估计会磨挺久

def cuteseq(seq):     longcute = [0] * len(seq)     for i in range(2, len(seq)):         end = 0         flag = False         for j in reversed(range(i)):             for k in reversed(range(j)):                 if (seq[k] + seq[j]) == seq[i]:                     flag = True                     end = j                     break             if flag:                 break         if flag:             longcute[i] = max(longcute[i-1], longcute[end]+1)         else:             longcute[i] = max(longcute[i-1], 0)     return longcute[-1]+2 动态规划的思想。保留最后一 个和不保留最后一个，分别计算最大可爱长度