Increasing Subsequence Recursive Java

Question

I have the following problem: A sequence of numbers is said to be monotonically increasing (or simply increasing) if every number in the sequence is greater than, or equals to, the number preceding it. write a boolean function increasing(int[] x, int length) that returns true if the given array contains an increasing subsequence of the given length, and false otherwise. The guidelines:

• No loops at all, only recursion
• No lists & imports (so no map or so) & ?
• No changing the signature of the function increasing(int[] x, int length)
• You may add private functions but not ints/booleans ect.

I thought about using an old problem, longest increasing subsequence, and then comparing the sizes, if the size given is larger then LIS, it would return false. However my code for LIS seems to be missing cases that skip a number and repeat a number, for example 9,7,5,4,7,1,-3,8 return false for 3 instead of true, also for 3,1,1,2 returns 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

Finding the longest increasing sequence seems like it may be the harder problem to solve in this case. The problem of finding consecutive sequences of a certain length simply requires adding one to an index variable at each level down the recursive call stack, and comparing to your target length. So, in the simple case, your problem can be solved like this:

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

It becomes more complex when you have to account for sequences of non-consecutive items. In that case, rather than immediately returning false when you encounter an element that's less than its predecessor, you simply move down the call stack without incrementing the depth, and keep track of how many elements to skip when comparing the last two terms of the sequence. (Note, this requires an extra check to prevent the recursion from exceeding the array size):

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

Answer 2

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

Demo:

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
}