Python Program to Find Longest Increasing Subsequence

You can find the longest increasing subsequence in Python by using dynamic programming with dp array where dp[i] stores the length of the longest increasing subsequence ending at index i. The code is: def lis(arr): dp = [1]*len(arr); for i in range(len(arr)): for j in range(i): if arr[j] < arr[i]: dp[i] = max(dp[i], dp[j]+1); return max(dp) if arr else 0.

Examples

Input[10, 22, 9, 33, 21, 50, 41, 60]

Output5

Input[3, 10, 2, 1, 20]

Output3

Input[3, 2]

Output1

How to Think About It

To find the longest increasing subsequence, think about each number as a potential end of a sequence. For each number, check all previous numbers to see if you can extend a smaller subsequence by adding the current number. Keep track of the longest length found so far for each position, then pick the maximum length at the end.

Algorithm

1

Create a list dp of the same length as input, filled with 1s because each element alone is a subsequence.

2

For each element from left to right, check all previous elements.

3

If a previous element is smaller, update dp at current index to max of current dp or dp at previous index plus one.

4

After filling dp, find the maximum value in dp which is the length of the longest increasing subsequence.

5

Return this maximum value.

Code

python

def lis(arr):
    dp = [1] * len(arr)
    for i in range(len(arr)):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp) if arr else 0

# Example usage
arr = [10, 22, 9, 33, 21, 50, 41, 60]
print(lis(arr))

Output

5

Dry Run

Let's trace the example [10, 22, 9, 33, 21, 50, 41, 60] through the code

1

Initialize dp

dp = [1, 1, 1, 1, 1, 1, 1, 1]

2

i=1, check j=0

arr[0]=10 < arr[1]=22, dp[1] = max(1, dp[0]+1) = 2, dp = [1, 2, 1, 1, 1, 1, 1, 1]

3

i=2, check j=0,1

arr[0]=10 < 9? No; arr[1]=22 < 9? No; dp unchanged

4

i=3, check j=0..2

arr[0]=10 < 33, dp[3]=max(1,1+1)=2; arr[1]=22 < 33, dp[3]=max(2,2+1)=3; arr[2]=9 < 33, dp[3]=max(3,1+1)=3; dp=[1,2,1,3,1,1,1,1]

5

i=4, check j=0..3

arr[0]=10 < 21, dp[4]=max(1,1+1)=2; arr[1]=22 < 21? No; arr[2]=9 < 21, dp[4]=max(2,1+1)=2; arr[3]=33 < 21? No; dp=[1,2,1,3,2,1,1,1]

6

i=5, check j=0..4

arr[0]=10 < 50, dp[5]=max(1,1+1)=2; arr[1]=22 < 50, dp[5]=max(2,2+1)=3; arr[2]=9 < 50, dp[5]=max(3,1+1)=3; arr[3]=33 < 50, dp[5]=max(3,3+1)=4; arr[4]=21 < 50, dp[5]=max(4,2+1)=4; dp=[1,2,1,3,2,4,1,1]

7

i=6, check j=0..5

arr[0]=10 < 41, dp[6]=max(1,1+1)=2; arr[1]=22 < 41, dp[6]=max(2,2+1)=3; arr[2]=9 < 41, dp[6]=max(3,1+1)=3; arr[3]=33 < 41, dp[6]=max(3,3+1)=4; arr[4]=21 < 41, dp[6]=max(4,2+1)=4; arr[5]=50 < 41? No; dp=[1,2,1,3,2,4,4,1]

8

i=7, check j=0..6

arr[0]=10 < 60, dp[7]=max(1,1+1)=2; arr[1]=22 < 60, dp[7]=max(2,2+1)=3; arr[2]=9 < 60, dp[7]=max(3,1+1)=3; arr[3]=33 < 60, dp[7]=max(3,3+1)=4; arr[4]=21 < 60, dp[7]=max(4,2+1)=4; arr[5]=50 < 60, dp[7]=max(4,4+1)=5; arr[6]=41 < 60, dp[7]=max(5,4+1)=5; dp=[1,2,1,3,2,4,4,5]

9

Find max in dp

max(dp) = 5

i	dp array
0	[1, 1, 1, 1, 1, 1, 1, 1]
1	[1, 2, 1, 1, 1, 1, 1, 1]
2	[1, 2, 1, 1, 1, 1, 1, 1]
3	[1, 2, 1, 3, 1, 1, 1, 1]
4	[1, 2, 1, 3, 2, 1, 1, 1]
5	[1, 2, 1, 3, 2, 4, 1, 1]
6	[1, 2, 1, 3, 2, 4, 4, 1]
7	[1, 2, 1, 3, 2, 4, 4, 5]

Why This Works

Step 1: Initialize dp array

Each element starts as a subsequence of length 1 by itself, so dp is filled with 1s.

Step 2: Compare elements to build subsequences

For each element, check all previous elements to see if you can extend a smaller subsequence by adding the current element.

Step 3: Update dp with longest subsequence length

If a previous element is smaller, update dp at current index to the longest subsequence length found so far plus one.

Step 4: Find the maximum length

The longest increasing subsequence length is the maximum value in dp after processing all elements.

Alternative Approaches

Binary Search Optimization

python

def lis_binary_search(arr):
    from bisect import bisect_left
    sub = []
    for x in arr:
        i = bisect_left(sub, x)
        if i == len(sub):
            sub.append(x)
        else:
            sub[i] = x
    return len(sub)

arr = [10, 22, 9, 33, 21, 50, 41, 60]
print(lis_binary_search(arr))

This method uses binary search to build a subsequence array, achieving better time complexity O(n log n) but is more complex to understand.

Recursive with Memoization

python

def lis_recursive(arr, prev_index, cur_pos, memo):
    if cur_pos == len(arr):
        return 0
    if (prev_index, cur_pos) in memo:
        return memo[(prev_index, cur_pos)]
    taken = 0
    if prev_index < 0 or arr[cur_pos] > arr[prev_index]:
        taken = 1 + lis_recursive(arr, cur_pos, cur_pos + 1, memo)
    not_taken = lis_recursive(arr, prev_index, cur_pos + 1, memo)
    memo[(prev_index, cur_pos)] = max(taken, not_taken)
    return memo[(prev_index, cur_pos)]

arr = [10, 22, 9, 33, 21, 50, 41, 60]
memo = {}
print(lis_recursive(arr, -1, 0, memo))

This recursive approach with memoization is easier to understand but less efficient than binary search, with O(n^2) time complexity.

Complexity: O(n^2) time, O(n) space

Time Complexity

The nested loops cause the algorithm to check pairs of elements, resulting in O(n^2) time.

Space Complexity

The dp array stores one value per element, so space is O(n).

Which Approach is Fastest?

The binary search method runs in O(n log n) and is faster for large inputs, but the dp method is simpler to learn.

Approach	Time	Space	Best For
Dynamic Programming	O(n^2)	O(n)	Small to medium arrays, easy to understand
Binary Search Optimization	O(n log n)	O(n)	Large arrays, performance critical
Recursive with Memoization	O(n^2)	O(n^2)	Learning recursion and memoization