Does there exist a Top Down Dynamic Programming solution for Longest Increasing Subsequence?

Question

I want to know how to find the LIS of an array using Top Down Dynamic Programming. Does there exist one such solution? Can you give me the pseudocode for finding the LIS of an array using Top Down Dynamic Programming? I am not able to find one on the internet. All of them use Bottom Up.

Answer 1

Recursive approach to solve LIS length in java would be like below -

 public int LIS(int[] arr) {
        return LISLength(arr, Integer.MIN_VALUE, 0);
    }

    public int LISLength(int[] arr, int prev, int current) {
        if (current == arr.length) {
            return 0;
        }
        int include = 0;
        if (arr[current] > prev) {
            include = 1 + LISLength(arr, arr[current], current + 1);
        }
        int exclude = LISLength(arr, prev, current + 1);
        return Math.max(include, exclude);
    }

But it would work with O(2^n) time complexity so we need to use memoization technique to reduce the complexity with below approach -

public int LIS(int[] arr) {
        int memoTable[][] = new int[arr.length + 1][arr.length];
        for (int[] l : memoTable) {
            Arrays.fill(l, -1);
        }
        return LISLength(arr, -1, 0, memoTable);
    }
    public int LISLength(int[] arr, int prev, int current, int[][] memoTable) {
        if (current == arr.length) {
            return 0;
        }
        if (memoTable[prev + 1][current] >= 0) {
            return memoTable[prev + 1][current];
        }
        int include = 0;
        if (prev < 0 || arr[current] > arr[prev]) {
            include = 1 + LISLength(arr, current, current + 1, memoTable);
        }

        int exclude = LISLength(arr, prev, current + 1, memoTable);
        memoTable[prev + 1][current] = Math.max(include, exclude);
        return memoTable[prev + 1][current];
    }

So O(n^2) would be optimized time complexity with memoization technique.