TikTok OA 面试复盘｜Concave Subsequence 为什么要找最远端点

TikTok OA 的 Longest Concave Subsequence 要求两端都大于中间元素，内部却不要求先降后升。把它套成最长递增子序列，会从第一步就建错状态。 2024 年这道 OA 题给的是 1 到 n 的排列，n 最大为 10 万。这里单独拆这一题。美国 Intern 的 2025 年记录另有 OA 后三轮面试；两份记录属于不同批次，不能拼成同一套试卷。

第一题：最长凹形子序列

题目描述

从排列中选一个保持原顺序的子序列，让首尾元素都严格大于内部所有元素，返回最大长度。子序列允许跳过元素，长度为 2 时没有内部元素。自拟演算例子： [5,1,6,2,4,3] 可以选 [5,1,2,4] ，长度为 4；中间的 6 被跳过。只比较相邻元素，无法判断这种子序列是否合法。

解题思路

固定两端中较小的值 v，位置为 p。另一个端点必须大于 v，中间只选小于 v 的数。在 p 的同一侧，把另一端移得更远，只会增加可选位置。因此每个 v 只需检查两个候选：所有大于 v 的元素中，最左和最右的位置。按 v 从 n 递减到 1 扫描。树状数组先在每个位置放 1；处理 v 时，优先把 p 位置减 1。此时数组恰好只统计小于 v 的元素。已经处理过的大值位置，用两个变量维护最小位置 L 和最大位置 R。若 L 在 p 左侧，查询开区间 (L,p) 的计数，加 2；若 R 在 p 右侧，同样查询 (p,R) 。更新答案后，再把 p 加入大值端点的范围。注意先删当前值、再查询、最后更新端点，否则会把 v 自己算进内部或两端。每对合法端点都有一个较小值，因此倒序扫描会覆盖它；最远端点包含原区间全部合格元素，答案不会变差。总时间 O(n log n)，额外空间 O(n)。长度为 1 的输入单独返回 1。

TikTok OA 练习检查

先用双重循环枚举两端，再直接数内部合格元素，做小规模对拍。重点检查严格递增、严格递减、最大值在中间，以及最优答案需要跳过大数的情况。不要给这个排列题擅自加入重复值；重复值版本需要按值分组更新。

FAQ

凹形是否要求内部单调？

不要求。内部元素只需小于两个端点，彼此之间可以上升或下降。

为什么不能把数组排序后求答案？

排序会破坏原位置顺序。可以按值处理，但树状数组必须建在原下标上。

严格递增时能选多少个？

n 至少为 2 时答案是 2。任意三个按原序选出的元素，中间值都会大于左端点。

参考来源

LeetCode：TikTok 凹形子序列题目 Reddit：TikTok AI 岗位 OA 经历 Taro：美国 TikTok Intern 面试经历

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

微信：Coding0201
邮箱：[email protected]
Telegram：@OAVOProxy
WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。