删除元素以对数组进行排序 [英] Removing elements to sort array

问题描述

我正在寻找一种对数组进行排序的算法，但不能通过移动值来实现。相反，我想删除尽可能少的值并以排序列表结尾。基本上，我想找到最长的升序子数组。

I'm looking for an algorithm to sort an array, but not by moving the values. Rather, I'd like to delete as few values as possible and end up with a sorted list. Basically I want to find the longest ascending sub-array.

举例说明：

1 4 5 6 7 2 3 8

应该成为（2个删除项）

Should become (2 removes)

1 4 5 6 7 8

而不是（5个删除项）

1 2 3

我可以看到如何以幼稚的方式做到这一点，即通过递归检查每个元素的删除和不删除树。我只是想知道是否有更快/更有效的方法来做到这一点。

I can see how I can do this in a naive way, i.e. by recursively checking both the 'remove' and 'dont remove' tree for each element. I was just wondering if there was a faster / more efficient way to do this. Is there a common go-to algorithm for this kind of problem?

推荐答案

您正在寻找最长的增加子序列问题。有一个算法可以在O（n log n）时间内解决该问题。

You're looking for the longest increasing subsequence problem. There is an algorithm that solves it in O(n log n) time.

这篇关于删除元素以对数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！