递归算法从列表中选择递增的非连续数字

Question

我需要编写一个函数,在一个数字列表中找到最长的,不一定是连续的,升序的子序列.该函数需要递归.

我的算法有问题,我无法弄清楚如何解决它.这是一个示例起始列表:

[88,1,22,3,34,6,54,9,19]

正确的结果是:

[1,3,6,9,19]

我想在屏幕上打印这个子序列的长度,在这种情况下,5.

我的功能:

int subseires(int arraysub[], int small, int i, int j, int coun){
    if( i==size ) return 0;

    if( arraysub[i]>arraysub[j] )
        subseires(arraysub, small, i+1, j+1, coun);

    if( arraysub[i]<arraysub[j] )
        subseires(arraysub, small, i, j+1, coun+1);

    return coun;
}

任何人都可以指出我的程序的问题吗？

Answer 1

你的算法可能是错误的。

你需要做的是对于数组的每个成员 - 如果你可以选择它（它不小于你选择的前一个），然后递归地检查两个选项：选择它或不选择它。这样您就可以一直走到数组末尾并返回总长度。最后打印最长的长度。

尝试在 C 函数中实现该算法。