Увеличение подпоследовательности рекурсивной Java

Question

У меня есть следующая проблема: говорят, что последовательность чисел монотонно увеличивается (или просто увеличивается), если каждое число в последовательности больше или равно числу, предшествующему ей. написать булеву функцию increasing(int[] x, int length) возвращает true, если данный массив содержит возрастающую подпоследовательность заданной длины, и false в противном случае. Рекомендации:

• Никаких петель, только рекурсия
• Нет списков и импорта (так что нет карты или около того) и ?
• Нет изменения подписи функции increasing(int[] x, int length)
• Вы можете добавить частные функции, но не intts/booleans и т. Д.

Я подумал об использовании старой проблемы, самой длинной увеличивающейся подпоследовательности, а затем о сравнении размеров: если заданный размер больше, чем LIS, он вернет false. Однако мой код для LIS, кажется, пропускает случаи, которые пропускают число и повторяют число, например 9,7,5,4,7,1,-3,8 вернуть false для 3 вместо true, также для 3,1,1,2 возвращает ложь

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, x[0], 0, 0) >= length;
}

private static int increasing(int[] x, int length, int min, int i, int from) {
    if (i >= x.length)
        return 0;    

    int res = increasing(x, length, Math.max(min, x[i]), i + 1, from);

    if (x[i] >= min)
        res++;    
    if (i != from || res >= length || i + length > x.length)
        return res;
    return increasing(x, length, x[i + 1], i + 1, i + 1);
}

Демо - версия:

public static void main(String... args) {
    System.out.println(increasing(new int[] { 3, 1, 1, 2 }, 3));    // true
    System.out.println(increasing(new int[] { 9, 7, 5, 4, 7, 1, -3, 8 }, 3));   // true
}

Answer 2

Поиск самой длинной увеличивающейся последовательности может показаться более сложной задачей в этом случае. Проблема поиска последовательных последовательностей определенной длины просто требует добавления единицы в индексную переменную на каждом уровне вниз по стеку рекурсивных вызовов и сравнения с целевой длиной. Итак, в простом случае, ваша проблема может быть решена так:

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);
}