请教这道算法题的思路：一串数字，一次只能将一个任意位置的数字放到最左或最右的位置，求需要几次能将这串数字改为升序的？
Newyorkcity · 2020-09-22 12:53:26 +08:00 · 1109 次点击这是一个创建于 1553 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目保证这串数字中没有相同的
4 1 2 5 3 需要两次
第一次 1 2 5 3 4
第二次 1 2 3 4 5
谢谢
4 1 2 5 3 需要两次
第一次 1 2 5 3 4
第二次 1 2 3 4 5
谢谢
 |
1
binux 2020-09-22 12:58:24 +08:00 via Android
查找最大连续子串，剩下的拿出来往头尾塞就行了
|
 |
2
Newyorkcity OP @binux 你这个例子就通不过吧。。。最大连续子串是 1 2，塞 4 5 3 三次，就比答案的两次多了。。。
|
|
3
binux 2020-09-22 13:16:39 +08:00 via Android
@Newyorkcity 我是说 123 连续字串
|
 |
4
kop1989 2020-09-22 13:29:23 +08:00
必须要最优解么？感觉好像很困难的样子。
或者需要确认一些细节，比如数字一定连续么？ |
 |
7
Procumbens 2020-09-22 13:37:17 +08:00
应该就是找 longest increasing subsequence
|
 |
8
justforlook44444 2020-09-22 14:03:37 +08:00
最长排序子串
|
|
9
justforlook44444 2020-09-22 14:05:37 +08:00
最长有序子序列
|
 |
10
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 按顺序拿出来往头尾塞就行了
|
Select Language