牛妹的面试

[编程题]牛妹的面试

热度指数：3013 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

众所周知，牛妹是一个offer收割姬，这次面试她遇到了这样的一个问题。

给了一个序列，让找出最长的“凸子序列”

何为“凸子序列”：数列中有一个x_i,使得所有x₀<x₁<x₂….x_i-1<x_i且x_i>x_i+1>x_i+1>….>x_n

eg：12345431,是山峰序列，12345234不是山峰序列

注：单调递增或单调递减序列也算山峰序列；单独一个数是长度为1的山峰序列

示例1

输入

[1,2,3,6,1]

输出

示例2

输入

[1,2,2,1]

输出

说明

1,2,1

备注:

给定的序列中数都大于0 且不超过10000，且序列长度不超过1000

算法知识视频讲解

Miss.Zhou

发表于 2020-02-06 17:07:10

看到这个题，很明显会想到是两个“最长上升子序列”从左到右，从右到左各一遍，然后拼在一起即可。关于最长上升子序列，普通解法是![图片说明](https://www.nowcoder.com/equation?tex=n%5E%7B2%7D "图片标题") 的时间复杂度代码如下： class Solut 展开全文

Maokt

发表于 2021-07-31 14:49:03

算法思想一：动态规划+两次遍历解题思路：最长上升子序列的衍生题，所谓最长凸子序列从左边到峰顶的序列是从左到右的最长上升子序列，从峰顶到右侧的序列是从右到左的最长上升子序列因此可以采用从左到右计算一次各个子序列的最长上升子序列 l2r（其中l2r[i]表示以i结束的最长展开全文

球球了给孩子一个offer吧

发表于 2021-07-31 16:14:12

描述：众所周知，牛妹是一个offer收割姬，这次面试她遇到了这样的一个问题。给了一个序列，让找出最长的“凸子序列”何为“凸子序列”：数列中有一个xi,使得所有x0<x1<x2….xi-1<xi且xi>xi+1>xi+1>….>xneg：12345431,是山展开全文

CroMarmot

发表于 2021-10-04 01:57:58

题意给定数组。找一个子序列，满足先严格递增后严格递减，求最大的子序列长度数组长度 ≤1000\leq 1000≤1000 方法 dfs(TLE) 我们枚举每一个位置，假设这个位置是顶点，从这个顶点向两侧深度搜索。搜索的设计为，遍历点。如果一个点可选，则考虑选择改点并继续深搜，深搜返回后遍历展开全文

牛客534170409号

发表于 2021-08-04 17:01:24

题目描述众所周知，牛妹是一个offer收割姬，这次面试她遇到了这样的一个问题。给了一个序列，让找出最长的“凸子序列” “凸子序列”：数列中有一个,使得所有且 eg：12345431,是山峰序列，12345234不是山峰序列注：单调递增或单调递减序列也算山峰序列；单独一个数是长度为1的山峰序列展开全文