微软算法面试题:如何找最长的增长子序列

本文由码农网 – 小峰原创翻译,转载请看清文末的转载要求,欢迎参与我们的付费投稿计划

这个问题是微软提出来的。

给定一组数字,找出数组中最长的增长子序列的长度。子序列不一定必须是连续的。

例如,给定数组[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15],最长的增长子序列的长度为6:它是0,2,6,9,11,15。

解决方案

解决这个问题的蛮力方法是生成每个可能的子序列,然后测试每个子序列的单调性并保持跟踪最长的那个。这将非常昂贵:生成每个子序列就得O(2^N)!

相反,我们可以试着用递归来解决这个问题,然后用动态编程来优化。

假设我们已经有了一个函数,这个函数给了我们最长增长子序列的长度。然后我们将试着将输入数组的一部分反馈给它并尝试扩展结果。基本情况是:空列表,返回0;有一个元素的数组,返回1。

然后

  • 对于直到倒数第二个元素为止的每个索引i,计算longest_increasing_subsequence到那里为止。
  • 如果最后一个元素大于arr[i],我们就用最后一个元素来扩展结果(因为否则它就不是增长的了)。
  • 保持跟踪最大的结果。
def longest_increasing_subsequence(arr):
    if not arr:
        return 0
    if len(arr) == 1:
        return 1

    max_ending_here = 0
    for i in range(len(arr)):
        ending_at_i = longest_increasing_subsequence(arr[:i])
        if arr[-1] > arr[i - 1] and ending_at_i + 1 > max_ending_here:
            max_ending_here = ending_at_i + 1
    return max_ending_here

由于重复的子计算(指数时间),所以这会非常非常慢。因此,让我们通过动态编程来存储值以便稍后重新计算它们。

我们将储存一个长度为N的数组A,并且A[i]将包含以i结尾的最长增长子序列的长度。然后,我们可以使用相同的递归循环,转而在数组中查找:

def longest_increasing_subsequence(arr):
    if not arr:
        return 0
    cache = [1] * len(arr)
    for i in range(1, len(arr)):
        for j in range(i):
            if arr[i] > arr[j]:
                cache[i] = max(cache[i], cache[j] + 1)
    return max(cache)

现在的时间复杂度和空间复杂度为O(N^2)和 O(N)。

你是正在准备面试编程工作,还是正享受于编程的乐趣中?不管怎样,知识是靠积累的。祝编码快乐!

译文链接:http://www.codeceo.com/article/find-the-longest-increasing-subsequence.html
英文原文:How to Find the Longest Increasing Subsequence
翻译作者:码农网 – 小峰
转载必须在正文中标注并保留原文链接、译文链接和译者等信息。]