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.

Brancusi

python solution can be found below. – Subjacent

Answer 1

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]

Heinrik

It's incorrect, I believe. Try array = [1, 5, 2, 3, 4, 7, 2]. – Grassofparnassus

@Dhruv Is there still any question about my answer? Please don't hesitate to leave a comment here to ask me. – Heinrik

Answer 2

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.

Supposititious

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

Ovalle

Please read this: Why should I not #include <bits/stdc++.h>? When you have done so, edit the code in your answer to use standard header files. – Marquetry

Also, explaining your code could help others understanding :) – Deadeye

Answer 4

Yes there exists a top down recursive memoized version.

Every element of array, if larger than the previous element, has a choice either to be part of the increasing subsequence or not.

If it is not part of the increasing subsequence, we ignore the element and dont add it to the length of the subsequence.

Finally we need to return maximum of the two choices we made.

Below you can find the python code.

class Solution:
    def longestSubsequence(self,a,n):
        '''
        Every element, if larger than the prev ele, has a choice, be a part of the increasing subseq or not be
        '''
        memo = {}
        
        def solve(i,prev):
            if i>=n:
                return 0
                
            ky = (i,prev)
            if ky in memo:
                return memo[ky]
                
            ways1 = 0
            if prev==None:
                ways1 = 1+solve(i+1,a[i])
            elif a[i]>prev:
                ways1 = 1 + solve(i+1,a[i])
                
                
            ways2 = solve(i+1,prev)
            
            memo[ky] = max(ways1,ways2)
            return memo[ky]
            
        return solve(0,None)

Here the dictionary will serve as the memoization data structure.The key is the pair <indx,prev> since both might change in every iteration.

We can use this memo to retrieve overlapping sub problems.

Subjacent

Answer 5

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

Bedight

Um, This is bottom-up approach. OP asks for top-down, which is recursion + memoization. – Torrey