C++实现最长连续递增子数组长度的递归函数求解咨询

问题背景 #

需要用C++编写递归函数，求解整数数组的最长连续递增子数组长度，要求使用指定代码框架，函数内不能包含循环或额外函数。例如数组1,2,4,6,4,21,21,22,0,1,3,5,100,7的结果为5（对应0,1,3,5,100这5个元素）。

给定的代码框架如下：

#include <stdio.h>
#define MAX_SIZE 1000
int get_max_series(int a[], int size);
int main() {
    int i, size_array, array[MAX_SIZE];
    scanf("%d", &size_array);
    for (i = 0; i < size_array; i++)
        scanf("%d", &array[i]);
    printf("%d", get_max_series(array, size_array));
    return 0;
}
int get_max_series(int a[], int size) {
    // 我的代码需写在此处
}

你的代码问题 #

你尝试编写的代码无法在递减对出现时重置计数器，导致只能计算从数组起始位置开始的连续递增长度，无法跟踪全局最长序列：

#include <stdio.h>
#define MAX_SIZE 1000
int get_max_series(int a[], int size);
int main() {
    int i, size_array, array[MAX_SIZE];
    scanf("%d", &size_array);
    for (i = 0; i < size_array; i++)
        scanf("%d", &array[i]);
    printf("%d", get_max_series(array, size_array));
    return 0;
}
int get_max_series(int a[], int size) {
    if (size == 1)
        return 1;
    if (a[0] < a[1])
        return 1 + get_max_series(&a[1], size - 1);
    return get_max_series(&a[1], size - 1);
}

问题分析 #

你的代码逻辑是从数组开头往后递归，遇到递增就累加长度，遇到递减就跳过当前元素继续递归，但没有记录之前的最长长度，也没有在递增中断时重置当前的连续计数。比如在示例数组中，当遇到6>4时，代码会直接返回后面序列的长度，但实际上我们需要比较之前的最长长度和后续新序列的长度，取最大值。

解决方案 #

由于不能修改给定的函数签名，也不能使用循环或额外函数，我们可以用静态变量来跟踪全局最长长度，同时让递归函数返回当前位置开始的连续递增长度，供上层递归计算使用。

完整的修改代码如下：

#include <stdio.h>
#define MAX_SIZE 1000
int get_max_series(int a[], int size);
int main() {
    int i, size_array, array[MAX_SIZE];
    scanf("%d", &size_array);
    for (i = 0; i < size_array; i++)
        scanf("%d", &array[i]);
    printf("%d", get_max_series(array, size_array));
    return 0;
}
int get_max_series(int a[], int size) {
    // 静态变量，仅初始化一次，用于记录全局最长长度
    static int max_len = 0;
    int current_len;

    if (size == 1) {
        // 处理最后一个元素，当前长度为1
        current_len = 1;
        if (current_len > max_len) {
            max_len = current_len;
        }
        // 递归结束前重置静态变量，避免影响下次函数调用
        int result = max_len;
        max_len = 0;
        return result;
    }

    // 先递归处理后续子数组，获取从下一个元素开始的连续长度
    int next_current = get_max_series(a + 1, size - 1);

    if (a[0] < a[1]) {
        // 当前元素与下一个递增，当前长度 = 后续连续长度 + 1
        current_len = next_current + 1;
    } else {
        // 递增中断，当前长度重置为1
        current_len = 1;
    }

    // 更新全局最长长度
    if (current_len > max_len) {
        max_len = current_len;
    }

    // 返回当前连续长度，供上层递归计算使用
    return current_len;
}

代码工作原理 #

1. 静态变量max_len：用来全程记录遍历过程中遇到的最长连续递增子数组长度，只会在第一次进入函数时初始化。
2. 递归方向：从数组末尾往回计算，每次先处理后续子数组，拿到后续的连续长度后，再判断当前元素是否能延续这个递增序列。
3. 长度计算：
   • 如果当前元素小于下一个元素，当前连续长度就是后续长度加1；
   • 如果不满足递增，当前长度重置为1，代表新序列的开始。
4. 静态变量重置：在递归的终止条件（size == 1）中，我们保存最终结果后重置max_len，确保下次调用函数时不会残留之前的计算值。

这段代码可以正确处理示例数组，返回结果5，完全符合你的需求。

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