【问题】请教一道面试算法问题

zoeshaw

2019/9/23镜像同步12 回复

题目大意：给定一个数组，求数组能否分成几个子序列（下标不一定连续的子数组），每个子序列都是单调不减的且元素个数大于等于3个注：不能用回溯或者递归，有没有更好的方法解答呢？

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

a940100079机器人#1 · 2019/9/23

有一个想法，基于最长递归子序列 1.找出最长递归子序列，把对应下标的元素从数组删除 2.重复（1）的操作，直至找不到最长递归子序列或者最长递归子序列长度<3 时间复杂度优于n**2 或者接近n其实

Viredery机器人#2 · 2019/9/23

我也觉得像是贪心？但你的这个方法，对于下面这个例子 1 2 3 4 1 5 6 -> 1 2 3 4 5 6，剩了1 但实际可以 1 2 3 4 和1 5 6 【在 a940100079 的大作中提到: 】 : 有一个想法，基于最长递归子序列 : 1.找出最长递归子序列，把对应下标的元素从数组删除 : 2.重复（1）的操作，直至找不到最长递归子序列或者最长递归子序列长度<3 : ...................

a940100079机器人#3 · 2019/9/23

所以多加一步，当序列空了，或者啥，需要去已经探索到的长序列找位置，切割？我在寻思寻思【在 Viredery 的大作中提到: 】 : 我也觉得像是贪心？但你的这个方法，对于下面这个例子 : 1 2 3 4 1 5 6 : -> : ...................

zoeshaw机器人#4 · 2019/9/23

没太明白？【在 melonboo 的大作中提到: 】 : 判断最大两个数是不是在前两位，最小两个数是不是在后两位，长度小于六必须递增

zoeshaw机器人#5 · 2019/9/23

最基本就是回溯，但是面试官说有更好的方法【在 a940100079 的大作中提到: 】 : 有一个想法，基于最长递归子序列 : 1.找出最长递归子序列，把对应下标的元素从数组删除 : 2.重复（1）的操作，直至找不到最长递归子序列或者最长递归子序列长度<3 : ...................

zoeshaw机器人#6 · 2019/9/23

贪心能解妈？主要是每次构造序列在元素个数等于3的时候不知道还是不是应该继续加后面的数，这里必然存在加/不加两个选择，还是一个回溯的思想，不知道dp可行不？【在 Viredery 的大作中提到: 】 : 我也觉得像是贪心？但你的这个方法，对于下面这个例子 : 1 2 3 4 1 5 6 : -> : ...................

Viredery机器人#7 · 2019/9/23

我感觉要先找个递减序列，这个递减序列里的每个值就是每个子序列的开头【在 zoeshaw 的大作中提到: 】 : 贪心能解妈？主要是每次构造序列在元素个数等于3的时候不知道还是不是应该继续加后面的数，这里必然存在加/不加两个选择，还是一个回溯的思想，不知道dp可行不？ :

intmain机器人#8 · 2019/9/23

a940100079机器人#9 · 2019/9/23

我说的好像不是回溯吧。。是贪心【在 zoeshaw 的大作中提到: 】 : 最基本就是回溯，但是面试官说有更好的方法