如何递归定义数组最长振荡子序列（Longest Oscillating Subsequence）的长度？

直接在if语句后添加LOS(max(counter1,counter2))无法正确实现递归逻辑，核心问题是这种调用方式丢失了递归必需的状态信息，具体原因和正确思路如下：

问题根源 #

最长振荡子序列的递归需要跟踪当前子序列的结尾趋势（最后一步是上升还是下降），而你只传递了计数器的最大值，没有记录当前是处于上升态还是下降态，后续递归无法判断下一个元素是否符合振荡要求，自然无法正确延续计算。

正确的递归思路 #

递归的核心是拆解子问题，LOS的递归需要维护两个关键状态：

• up_len：以当前元素结尾、最后一步为上升（即当前元素 > 前一个元素）的最长振荡子序列长度
• down_len：以当前元素结尾、最后一步为下降（即当前元素 < 前一个元素）的最长振荡子序列长度

具体递归逻辑：

1. 终止条件：当处理到数组最后一个元素时，返回max(up_len, down_len)
2. 状态转移：
   • 若当前元素X[i] > X[i-1]：新的up_len = 之前的down_len + 1（从下降趋势转为上升），down_len保持不变
   • 若当前元素X[i] < X[i-1]：新的down_len = 之前的up_len + 1（从上升趋势转为下降），up_len保持不变
   • 若元素相等：两个状态都保持不变（相等元素无法加入振荡序列）
3. 递归传递：每一步将更新后的up_len和down_len传递给下一层递归，继续处理下一个元素

简单递归实现示例 #

def los_recursive(arr, idx, up_len, down_len):
    # 处理到数组末尾，返回当前最长长度
    if idx == len(arr):
        return max(up_len, down_len)
    
    # 初始处理（第二个元素，和第一个元素比较）
    if idx == 1:
        if arr[idx] > arr[idx-1]:
            return los_recursive(arr, idx+1, 2, 1)
        elif arr[idx] < arr[idx-1]:
            return los_recursive(arr, idx+1, 1, 2)
        else:
            return los_recursive(arr, idx+1, 1, 1)
    
    # 非初始状态的状态转移
    new_up, new_down = up_len, down_len
    if arr[idx] > arr[idx-1]:
        new_up = down_len + 1
    elif arr[idx] < arr[idx-1]:
        new_down = up_len + 1
    
    return los_recursive(arr, idx+1, new_up, new_down)

# 对外调用接口
def longest_oscillating_subsequence(arr):
    if len(arr) <= 1:
        return len(arr)
    # 初始时，单个元素的上升/下降长度都是1，从第二个元素开始处理
    return los_recursive(arr, 1, 1, 1)

总结 #

你之前的写法没有传递递归必需的趋势状态，导致递归无法正确判断后续元素的合法性，因此不能得到正确结果。必须通过跟踪上升、下降两种状态的长度，才能实现正确的递归逻辑。

内容的提问来源于stack exchange，提问作者KuriousKat