查找数组中最大的递增子集（非连续） [英] finding largest increasing subset of an array (non-contiguous)

问题描述

如何找到数组中最大的递增（非连续）子集？例如，如果A = array（50,1,4,9,2,18,6,3,7,10），则最大增加的非连续子集为（1,4,6,7,10）或（ 1,2,6,7,10）。我可以直观地看到如何找到子集，但是我不知道如何设计算法。

How can I find the largest increasing (non-contiguous) subset of an array? For example, if A= array(50,1,4,9,2,18,6,3,7,10) the largest increasing non-contiguous subset is either (1,4,6,7,10) or (1,2,6,7,10). I can intuitively see how to find the subset, but I don't know how to design the algorithm.

推荐答案

维基百科具有伪高效算法的代码：

Wikipedia has pseudo-code for an efficient algorithm:

http： //en.wikipedia.org/wiki/Longest_increasing_subsequence_problem

这篇关于查找数组中最大的递增子集（非连续）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！