三好学生 + 关注

签名:好好学习,天天向上

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

发表于 5个月前   1279次查看    0评论  3 赞

weiruan-longest.jpg

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

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

例如,给定数组[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],我们就用最后一个元素来扩展结果(因为否则它就不是增长的了)。

  • 保持跟踪最大的结果。

1
2
3
4
5
6
7
8
9
10
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结尾的最长增长子序列的长度。然后,我们可以使用相同的递归循环,转而在数组中查找:

1
2
3
4
5
6
7
8
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

3人已赞


本文由Fun言网 – 三好学生创作,转载请务必附上本文链接和出处,欢迎参与我们的付费投稿计划


你还没有登录,请先 登录注册!
文章评论0