c - 仅使用一个辅助递归函数求最长递增子序列的长度

Question

我需要仅使用单个递归函数找到最长单调递增子序列的长度。 例如，给定一个 arr={45 1 21 3 33 6 53 9 18} 它需要返回 5。我已经开始编写代码，但我被卡住了，我不知道如何找出哪个调用给出了最大长度。

函数longestSet是我的辅助函数，我可以使用我想要的任何变量，但必须从函数max_set调用它。

void question3(int question)
{
    int *arr, size;
    printf("enter the array size\n");
    scanf("%d", &size);
    arr=(int*)malloc(size*sizeof(int));
    fillArr(arr, size-1);
    max_set(arr, size);
    free(arr);
}

void max_set(int arr[], int size)
{
    int i=0, finelmax=0, count=0,longrising;
    longrising=longestSet(arr,size,i,finelmax,count);
    printf("the length of the longest risind set is: %d", longrising);
}

int longestSet(int arr[], int size, int i, int finelmax, int count)
{
    if(i==size)
        return count;

    if(arr[i]>=finelmax)
    {
        finelmax=arr[i];
        return longestSet(arr,size,i+1,finelmax,count+1);
    }

    return longestSet(arr,size,i+1,finelmax,count);
}

Answer 1

类似这样的事情:

int longestSet(int arr[], int size, int i, int finelmax, int count)
{
    if(i==size) return count;

    int length1 = longestSet(arr, size, i + 1, finelmax, count);
    if(arr[i] > finelmax)
    {
        int length2 = longestSet(arr, size, i + 1, arr[i], count + 1);
        if(length2 > length1) length1 = length2;
    }

    return length1;
}

这基本上所做的就是在每个点上比较是否包含当前数字或跳过它更好。而且也会很慢 - 例如，您可以添加内存来改进，但我猜这不是作业的一部分？