c - 使用递归和无循环查找数组中最长的升序子系列的长度

Question

我已经被困了几个小时，试图弄清楚如何编写一个函数来获取整数数组，并使用递归和完全不使用循环来找到数组中最长的递增子系列的长度。我只允许使用另一个 1 个递归函数 例如，对于以下数组:{45,1,21,3,3,6,53,9,18} outpot 应该是 5，因为最长的子系列是 {1,3,6,9,18 }. 所以，基本上，一个获取数组及其大小的函数，需要打印最长子系列的长度，完全不使用循环，不使用全局/静态类型，它可能使用另一个“帮助”递归函数，就是这样它。 这几乎是我想出的全部，而且一团糟而且效果不佳。 我一直在尝试扫描数组，而我一直都知道我正在查看的当前索引、与当前索引进行比较的索引以及我从中开始当前子系列的原始索引。 我在知道应该比较的索引的同时尝试扫描数组，但我被卡住了，这就是我得到的，我非常感谢任何提示和建议。 谢谢。

void max_set(int arr[], int size)
{
    int bigSeries[2] = { 0 };
    calcSeries(arr, bigSeries,0, 0, 1, size -1, 1);
    printf("number of max parts going up %d \n", bigSeries[0]);

}
 void calcSeries(int arr[], int bigSeries[],int originalCHeckedIndex, int checkedIndex,      int currentIndex, int lastIndex, int ascending)
{
    if ((checkedIndex == lastIndex) || (currentIndex > lastIndex))
    {
        if (ascending > bigSeries[0])
            bigSeries[0] = ascending;
        if (originalCHeckedIndex == lastIndex)
            return;
        else
        {
            calcSeries(arr, bigSeries, originalCHeckedIndex + 1, originalCHeckedIndex + 1, originalCHeckedIndex + 2, lastIndex, 0);
            return;
        }
    }
    if (arr[currentIndex] > arr[checkedIndex])
    {
        calcSeries(arr, bigSeries, originalCHeckedIndex, currentIndex, currentIndex + 1, lastIndex, ascending + 1);
    }
    else
    {
        if (arr[originalCHeckedIndex] < arr[currentIndex])
            calcSeries(arr, bigSeries, currentIndex, currentIndex, currentIndex + 1, lastIndex,ascending);
        calcSeries(arr, bigSeries, originalCHeckedIndex, checkedIndex, currentIndex + 1, lastIndex, ascending);
    }
}

Answer 1

该算法与第一个答案有很多相似之处，但涵盖了一些您可能需要注意的极端情况。我没有写冗长的评论，而是选择写一个新的答案。

完整性检查

像我在函数 max_set() 中所做的那样，对数组进行一些健全性检查。

• 是否提供了数组(检查 NULL)？
• 提供的数组大小是否至少为正数(考虑 size_t)？

允许值

数据类型int 允许正值和 负值。该算法应该同时处理这两者。至少我没有从你的帖子中读到他们必须是积极的。如果您跳过该部分，我的代码看起来会好一些。

递归

此算法(以及第一个答案中的算法)的思想是递归遍历数组，从第一个元素开始，最后结束。所以这已经定义了递归的开始和结束，如源代码中所述。

要以这种方式找到最长的数字子系列，总是存在三种可能性:

• 可以通过跳过当前处理的数来达到最长的子系列
• 将当前处理的个数相加可以得到最长的子系列
• 当前处理的数量放不下

如果一个数字大于先前添加的最大数字，则可以添加；毕竟我们要寻找一个上升的系列。当前的数字可能比数组中必须处理的其他数字大。因此，我们必须考虑两种可能性:在没有它和有它的情况下继续递归步骤——只要它符合条件。

可能的疏忽

考虑到 INT_MIN，机器上可能的最小整数值，是数组中完全有效的数字。我添加了变量seen，它只记录是否在数组中至少看到了一次 INT_MIN。第一次遇到时，seen 从 0 翻转到 1，由于 ascending 子系列的要求，不允许任何进一步的 INT_MIN 值。您的示例通过两次出现的数字 3 显示了此要求。

测试

尝试寻找各种测试用例，有时跳出框框思考。数组为 NULL，负大小，空数组。接下来，添加奇特的值，如负数、INT_MIN。或者创建升序系列、降序系列、交错系列。多次出现的数字 ...

#include <sys/limits.h>

#include <stdio.h>

int
analyze(int arr[], int size, int min, int seen)
{
    int sub_count = 0, count = 0;

    /* end of recursion */
    if (size == 0)
        return 0;

    /* recursion step, without and with current number */
    sub_count = analyze(arr + 1, size - 1, min, seen);
    if (arr[0] > min || (min == INT_MIN && arr[0] == INT_MIN && !seen))
        count = 1 + analyze(arr + 1, size - 1, arr[0], arr[0] == INT_MIN);

    /* return length of largest sub-series */
    return sub_count > count ? sub_count : count;
}

void
max_set(int arr[], int size)
{
    int seq = 0;

    if (arr != NULL && size > 0) {
        /* start of recursion */
        seq = analyze(arr, size, INT_MIN, 0);
    }

    printf("max sequence is %d\n", seq);
}

int
main(void)
{
    int arr[] = { 45, 1, 21, 3, 3, 6, 53, 9, 18 };
    max_set(arr, sizeof(arr) / sizeof(*arr));
    return (0);
}