Longest Increasing Subsequence

Definition

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

How it Works

For every element arr[i], we want to find the longest chain ending at i.

1. Look at all previous elements (j < i).
2. If arr[i] is bigger than arr[j], we can extend the chain ending at j.
3. LIS[i] = 1 + max(LIS[j]) for all valid j.

Example

Input: [10, 22, 9, 33, 21, 50, 41, 60] LIS: 10, 22, 33, 50, 60 Length: 5

Code Example (Java)

public class LIS_DP {

    public static int lis(int[] arr) {
        int n = arr.length;

        // Initialize LIS values for all indexes as 1
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }

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

        // Find maximum value in dp[]
        int max = dp[0];
        for (int i = 1; i  max) {
                max = dp[i];
            }
        }

        return max;
    }

    public static void main(String[] args) {
        int[] arr = {10, 22, 9, 33, 21, 50, 41, 60};

        System.out.println("Length of LIS is " + lis(arr)); // Output: 5
    }
}

Complexity Analysis

• Time Complexity: O(N^2) (Nested loops). Note: Can be optimized to O(N log N) using Binary Search.
• Space Complexity: O(N).