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.

Answer 2

Sure. Define:

F(n) = longest increasing subsequence of sequence 1..n , and the sequence must ends with element_n

Then we get that recursion function (Top down):

F(n) = max(len(F(i)) + 1) which 0 <= i < n and array[i] < array[n]

So the answer is:

Longest increasing subsequence of F(1..n)

With memoization, we come to this code(That's Python, it's better than pseudo-code):

d = {}
array = [1, 5, 2, 3, 4, 7, 2]

def lis(n):
    if d.get(n) is not None:
        return d[n]
    length = 1
    ret = [array[n]]
    for i in range(n):
        if array[n] > array[i] and len(lis(i)) + 1 > length:
            length = len(lis(i)) + 1
            ret = lis(i) + [array[n]]
    d[n] = ret
    return ret

def get_ans():
    max_length = 0
    ans = []
    for i in range(len(array)):
        if max_length < len(lis(i)):
            ans = lis(i)
            max_length = len(lis(i))
    return ans

print get_ans() # [1, 2, 3, 4, 7]

Answer 3

I always try to write the same logic as Top-Down and Bottom-Up. My Bottom-Up upproch:

#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;

int n;
vector<int> a, dp;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie();
    cin >> n;
    a.resize(n);
    dp.resize(n);
    for (auto &x : a) {
        cin >> x;
    }

    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], 1 + dp[j]);
            }
        }
    }

    int ans = *max_element(dp.begin(), dp.end());
    cout << ans << '\n';
}

Then I converted this solution as Top-Down:

#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;

int n;
vector<int> a, dp;

int calc(int i) {
    if (dp[i] != -1) {
        return dp[i];
    }

    dp[i] = 1;
    for (int j = i - 1; j >= 0; j--) {
        if (a[j] < a[i]) {
            dp[i] = max(dp[i], 1 + calc(j));
        }
    }

    return dp[i];
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie();
    cin >> n;
    a.resize(n);
    dp.resize(n, -1);
    for (auto &x : a) {
        cin >> x;
    }

    int ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        ans = max(ans, calc(i));
    } 

    cout << ans << '\n';
}

Answer 4

Top Down Approach

#include <iostream>
using namespace std;
int main()
{
    int t;cin>>t;
    while(t--){
    int n; cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];

    int lis[n];
    for(int i=0;i<n;i++) lis[i]=1;
    lis[0]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(arr[i]<arr[j] && lis[i]+1>lis[j])
                lis[j] = lis[i]+1;
        }
    }


    int ans = 1;
    for(int i=0;i<n;i++)
        ans = max(ans,lis[i]);
    cout<<ans<<endl;

    }
    return  0;
}