- 正确答案：拼接后数组的最大严格升序子序列（注意：题目中“严格升序串”应理解为**连续子数组**，即“严格递增的连续子段”，而非子序列；若理解为子序列则答案恒为n（因可无限复制，总能挑出任意长递增序列），显然不符合题意。故本题标准解读是：在无限拼接的数组A+A+A+…中，求最长的**连续严格递增子数组**（contiguous strictly increasing subarray）的长度。该长度存在上界，且可在O(n)时间内求出。最终答案为：若原数组本身严格递增 → 答案为 +∞（理论上无限长），但实际面试中要求输出“无限”或特殊标记；否则，答案 = max( 1. 原数组内部最长严格递增连续段长度（记为max_inc）， 2. 若数组尾部递增段可与头部递增段“跨边界衔接”，即存在k≥1使得 A[n−k..n−1] + A[0..m−1] 构成严格递增连续段，则取其最大可能长度。 ) 具体地，设： - tail_inc：从末尾开始的最长严格递增后缀长度（即满足 A[i] < A[i+1] < … < A[n−1] 的最大长度，从右往左扫描）； - head_inc：从开头开始的最长严格递增前缀长度（即满足 A[0] < A[1] < … < A[j] 的最大长度，从左往右扫描）； - 若 A[n−1] < A[0]，说明一次拼接可衔接，此时跨边界递增段长度 = tail_inc + head_inc； - 若 A[n−1] < A[0] 且 A[n−2] < A[n−1] < A[0] < A[1]，还可尝试更长？但注意：严格连续递增要求每一步都满足 a[i] < a[i+1]，因此最多只能衔接一次（因为第二次拼接引入 A[n−1], A[0], A[1]，而 A[n−1] < A[0] 已用，但 A[0] < A[1] 是head_inc的前提，已包含；再往后 A[1] < A[2] 也需成立——所以只要head_inc ≥ 2且tail_inc ≥ 2且A[n−1] A[0]），所以此时无法跨接，但可无限拼接得到无限长递增段 —— 因为A[n−1] < A[n] ≡ A[0]不成立，但A[n−1] < A[0]假，所以不能跨。然而，若整个数组递增，则拼接后序列为：...,A[0],A[1],...,A[n−1],A[0],A[1],...，此时A[n−1]与A[0]构成下降，因此最长连续递增段仍被截断在每个周期内，长度为n。但等等 —— 这与直觉矛盾？举例：A=[1,2,3]，拼接后为[1,2,3,1,2,3,1,2,3,...]，其中最长连续严格递增段是[1,2,3]（长3）或[2,3,1]（非递增）、[3,1]（降），所以确实是3。但如果A=[1,3,5,7,9,2]，则max_inc=5（[1,3,5,7,9]），tail_inc=1（仅[2]），head_inc=1（仅[1]），A[5]=2, A[0]=1 → 2<1? 否，故不跨，答案5。再例：A=[4,5,6,1,2,3]，则max_inc=3（[4,5,6]或[1,2,3]），tail_inc=3（[1,2,3]），head_inc=3（[4,5,6]），A[5]=3 < A[0]=4 → 满足，跨段长=6，即[4,5,6,1,2,3]本身是循环递增？不，4<5<6>1，所以[4,5,6]递增，[1,2,3]递增，但6>1，不满足。哦！重大纠正：跨边界要求的是 A[n−2] < A[n−1] < A[0] < A[1]，即整个衔接必须严格递增。因此tail_inc定义应修正为：从末尾开始的**最长严格递增后缀，且该后缀的首元素要小于A[0]**？不，这样逻辑混乱。正确方式是：重新严谨定义：设 inc_from_end[i] 表示以位置i为起点、向右延伸的最长严格递增连续段长度（在单个数组内）——但这是常规LIS连续版。更标准做法是： step1: 计算每个位置i的“向右最长递增长度” rlen[i]：从i开始向右，满足A[j]1 ⇒ head_inc=3 tail_inc: from end: 3>2? no, 2>1? no, 1<2<3 ⇒ check A[3]=1, A[4]=2, A[5]=3 → A[3]1 ⇒ head_inc=3 tail_inc: from end: A[4]=2

美团运维开发转正实习笔试编程题

全站热榜

创作者周榜