请教这道算法题的思路：一串数字，一次只能将一个任意位置的数字放到最左或最右的位置，求需要几次能将这串数字改为升序的？

2020-09-22 12:53:26 +08:00
 Newyorkcity
题目保证这串数字中没有相同的

4 1 2 5 3 需要两次
第一次 1 2 5 3 4
第二次 1 2 3 4 5


谢谢
1135 次点击
所在节点    问与答
10 条回复
binux
2020-09-22 12:58:24 +08:00
查找最大连续子串，剩下的拿出来往头尾塞就行了
Newyorkcity
2020-09-22 13:03:52 +08:00
@binux 你这个例子就通不过吧。。。最大连续子串是 1 2，塞 4 5 3 三次，就比答案的两次多了。。。
binux
2020-09-22 13:16:39 +08:00
@Newyorkcity 我是说 123 连续字串
kop1989
2020-09-22 13:29:23 +08:00
必须要最优解么？感觉好像很困难的样子。
或者需要确认一些细节，比如数字一定连续么？
xkeyideal
2020-09-22 13:32:37 +08:00
@binux 这叫最大不降子序列
binux
2020-09-22 13:33:46 +08:00
@xkeyideal 不能只是不降，还要连续
Procumbens
2020-09-22 13:37:17 +08:00
应该就是找 longest increasing subsequence
justforlook44444
2020-09-22 14:03:37 +08:00
最长排序子串
justforlook44444
2020-09-22 14:05:37 +08:00
最长有序子序列
maplelin
2020-09-22 14:44:12 +08:00
@Newyorkcity #2 1 楼的意思是忽略不连续的数组找到最大连续子串，比如 1，6，2，9，3，4，8，5，7 的最大连续子串是 12345，剩下的 6，7，8，9 按顺序拿出来往头尾塞就行了

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://tanronggui.xyz/t/709372

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX