这个问题是微软提出来的。
给定一组数字，找出数组中最长的增长子序列的长度。子序列不一定必须是连续的。
例如，给定数组[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):
ifnot arr:
return0
iflen(arr) == 1:
return1
max_ending_here = 0
fori in range(len(arr)):
ending_at_i = longest_increasing_subsequence(arr[:i])
ifarr[-1] > arr[i - 1] and ending_at_i + 1> max_ending_here:
max_ending_here = ending_at_i + 1
returnmax_ending_here
由于重复的子计算（指数时间），所以这会非常非常慢。因此，让我们通过动态编程来存储值以便稍后重新计算它们。
我们将储存一个长度为N的数组A，并且A[i]将包含以i结尾的最长增长子序列的长度。然后，我们可以使用相同的递归循环，转而在数组中查找：
def longest_increasing_subsequence(arr):
ifnot arr:
return0
cache = [1] * len(arr)
fori in range(1, len(arr)):
forj in range(i):
ifarr[i] > arr[j]:
cache[i] = max(cache[i], cache[j] + 1)
returnmax(cache)
现在的时间复杂度和空间复杂度为O(N^2)和 O(N)。
你是正在准备面试编程工作，还是正享受于编程的乐趣中？不管怎样，知识是靠积累的。祝编码快乐！
网友评论