LIS

(i).LIS -Recursive

Python Code


def lis_recursive(arr, n):
    if n == 1:
        return 1
    
    max_len_ending_here = 1
    
    for i in range(1, n):
        subproblem_len = lis_recursive(arr, i)
        if arr[i - 1] < arr[n - 1] and subproblem_len + 1 > max_len_ending_here:
            max_len_ending_here = subproblem_len + 1
            
    return max_len_ending_here

# Example usage
sequence = [10, 22, 9, 33, 21, 50, 41, 60, 80]
n = len(sequence)
result = lis_recursive(sequence, n)
print("Length of Longest Increasing Subsequence:", result)

(ii). LIS- Memoization(TOP DOWN)

Python Code


def lis_top_down(arr, n, prev_index, memo):
    if n == 0:
        return 0
    
    if memo[n][prev_index] != -1:
        return memo[n][prev_index]
    
    if prev_index == -1 or arr[n - 1] > arr[prev_index]:
        include_current = 1 + lis_top_down(arr, n - 1, n - 1, memo)
        exclude_current = lis_top_down(arr, n - 1, prev_index, memo)
        memo[n][prev_index] = max(include_current, exclude_current)
    else:
        memo[n][prev_index] = lis_top_down(arr, n - 1, prev_index, memo)
    
    return memo[n][prev_index]

def longest_increasing_subsequence(arr):
    n = len(arr)
    # Create a memoization table initialized with -1
    memo = [[-1] * (n + 1) for _ in range(n + 1)]
    return lis_top_down(arr, n, -1, memo)

# Example usage
sequence = [10, 22, 9, 33, 21, 50, 41, 60, 80]
result = longest_increasing_subsequence(sequence)
print("Length of Longest Increasing Subsequence:", result)

(iii). LIS- Tabulation(Bottom UP)

Python Code


def longest_increasing_subsequence(arr):
    n = len(arr)
    dp = [1] * n
    
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

# Example usage
sequence = [10, 22, 9, 33, 21, 50, 41, 60, 80]
result = longest_increasing_subsequence(sequence)
print("Length of Longest Increasing Subsequence:", result)