题目分析

这个题目有一些难度，有些类似于LIS(最长上升子序列)问题，但是难度比它大，因为不单单是上升问题，还要下降，并且两部分长度要相等，且中间的元素值相等。这应该如何求解呢？能否仍然利用上升子序列的思想去做呢？

DP

我们需要找到从初始位置到i的最长下降子序列lds_array，然后找到从j到最后位置的最长上升子序列lis_array。然后当array[i] = array[j]时，看最长下降子序列lds_array[i]的值，然后看最长上升子序列lis_array[j]的值，因为两个长度要相等，因此只能选择两者的较小值乘2作为有效的长度。

要强调的是，这个问题不需要写两种，虽然既要使用LIS，也要使用LDS。但是我们发现从初始位置到i是LDS问题，从j到最后位置是LIS问题，但是从最后位置到j位置是一个LDS问题，因此将数组逆序，再传入最长下降子序列函数，最后将得到的最长下降子序列长度再逆序即可。

这就是这个题目的思路，其实说到底还是LIS问题。有关LIS的解法可以参考Leetcode 300博客，里面有详细的说明。这里就不过多赘述，给出LDS的写法。

这个标题是使用动态规划求解LIS问题，求解LIS的**时间复杂度为$O(n^2)$，空间复杂度为$O(n)$。因为要遍历i和j，因此整体时间复杂度为$O(n^2)$，空间复杂度为$O(n)$**。

import sys


def LDS(array):
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if array[j] > array[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return dp


for line in sys.stdin:
    n = int(line.strip())
    array = [int(x) for x in sys.stdin.readline().strip().split()]
    lds_array = LDS(array)
    lis_array = LDS(array[::-1])[::-1]
    res = 0
    for i in range(n):
        for j in range(i + 1, n):
            if array[i] == array[j]:
                res = max(res, 2 * min(lds_array[i], lis_array[j]))
    print(res)

二分查找

整体的分析过程和动态规划方法完全相同。

这个标题是使用二分查找求解LIS问题，求解LIS的**时间复杂度为$O(nlog(n))$，空间复杂度为$O(n)$。因为要遍历i和j，因此整体时间复杂度为$O(n^2)$，空间复杂度为$O(n)$**。

import sys


def LDS(array):
    tmp = []
    res = []
    for x in array:
        if not tmp or tmp[-1] > x:
            tmp.append(x)
        else:
            left, right = 0, len(tmp)
            while left < right:
                mid = (left + right) // 2
                if tmp[mid] <= x:
                    right = mid
                else:
                    left = mid + 1
            tmp[left] = x
        res.append(len(tmp))
    return res


for line in sys.stdin:
    n = int(line.strip())
    array = [int(x) for x in sys.stdin.readline().strip().split()]
    lds_array = LDS(array)
    lis_array = LDS(array[::-1])[::-1]
    res = 0
    for i in range(n):
        for j in range(i + 1, n):
            if array[i] == array[j]:
                res = max(res, 2 * min(lds_array[i], lis_array[j]))
    print(res)

刷题总结

最长上升子序列问题太经典了，在面试笔试中会经常遇到它，因此小伙伴们一定，一定，一定要掌握。