java - 增加子序列递归Java

Question

我有以下问题:如果每个数字序列单调递增(或简单递增)序列中的数字大于或等于它前面的数字。编写一个 boolean 函数 increasing(int[] x, int length) 如果给定数组包含给定长度的递增子序列则返回 true，否则返回 false。准则:

• 完全没有循环，只有递归
• 没有列表和导入(所以没有 map )和 ?
• 不改变函数的签名 increasing(int[] x, int length)
• 您可以添加私有(private)函数，但不能添加整数/boolean 值等。

我想过用一个老问题，最长递增子序列，然后比较大小，如果给定的大小比 LIS 大，它会返回 false。但是，我的 LIS 代码似乎缺少跳过数字并重复数字的情况，例如 9,7,5,4,7,1,-3,8 为 3 返回 false 而不是true，对于 3,1,1,2 也返回 false。

public static boolean increasing(int[] x, int length) {
    int i = 0;
    int ans = longestIncreasing(x, length, i);
    return (ans >= length);
}

private static int longestIncreasing(int[] arr, int n, int i) {
    if (n == 0) {
        return 1;
    }

    int m = 1, temp;
    if (arr[i++] < arr[n--]) {
        temp = 1 + longestIncreasing(arr, n, i);
        if (temp > m) {
            m = temp;    //   m = max(m, 1 + _lis(arr, i));
        }
    }
    else {
        longestIncreasing(arr, n--, i++);
    }
    return m;
}

Answer 1

在这种情况下，寻找最长递增序列似乎是更难解决的问题。找到一定长度的连续序列的问题只需要在递归调用堆栈的每一层将索引变量加一，然后与目标长度进行比较。所以，在简单的情况下，你的问题可以这样解决:

public static boolean increasing(int[] x, int length) {
    return increasing(x, length, 0);
}

private static boolean increasing(int[] x, int length, int depth) {
    if (x.length < length) return false;
    if (depth >= length) return true;
    if (depth > 0 && x[depth - 1] > x[depth]) return false;

    return increasing(x, length, depth + 1);
}

当您必须考虑非连续项目的序列时，它会变得更加复杂。在这种情况下，当遇到小于其前身的元素时，不是立即返回 false，而是简单地向下移动调用堆栈而不增加深度，并跟踪比较时要跳过多少元素序列的最后两项。 (注意，这需要额外检查以防止递归超过数组大小):

public static boolean increasing(int[] x, int length) {
    return increasing(x, length, 0, 0);
}

private static boolean increasing(int[] x, int length, int depth, int skip) {
    if (x.length < length) return false;
    if (depth >= length) return true;
    if (depth + skip >= x.length) return false;

    if (depth > 0 && x[depth - 1] > x[depth + skip]) {
        return increasing(x, length, depth, skip + 1);
    }

    return increasing(x, length, depth + 1, 0);
}