数组的最长的、后续的、升序的子序列

Question

我被大学的作业卡住了。任务是找到一种递归然后动态编程的方法来计算数组中最长的、后续的、升序的子序列的长度。例如，如果数组为：{4，- 5，-3，-2，5，-2，0，3，2}，则最大长度为4，子序列为{-5，-3，-2，5}。我很难找到递归的方式，没有递归的方式，我就不可能找到动态的方式。

我尝试过编程，但我知道它是错误的，我不确定如何修复它：

public static int length(int[] arr,int j)
{
    if(arr.length == 1)
    {
        return 1;
    }
    if(j == 1)
    {
        if(arr[j-1] < arr[j])
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else
    {
        int c = length(arr,j-1);
        if(arr[j-1] < arr[j])
        {
            return 1 + c;
        }
        else
        {
            return 0;
        }
    }
}

Answer 1

试试这个：

int length(int index, int previous)
    {
       if(arr.length == (index+1))
            return 0;
       else 
           if(arr[index] > previous)
               return 1+length(index+1,arr[index]);
           else return length(index+1,previous)
    }

也许您不需要在每次递归调用中都通过创建静态变量来将数组作为参数提供，

Previous是子序列的最新元素