📏 Longest Increasing Subsequence (LIS) – Complete In-Depth Explanation

The **Longest Increasing Subsequence (LIS)** problem is a **dynamic programming problem** that finds the longest subsequence of a given sequence where the elements are **in increasing order** (not necessarily contiguous).

📌 Why is LIS Important?

• ✅ **Used in stock market analysis for trend prediction.**
• 🚀 **Helps in finding the longest ordered sequence in data.**
• 🔍 **Useful in bioinformatics for DNA sequencing.**
• 📡 **Applied in computer vision for motion analysis.**

📌 Understanding LIS with an Example

Given an array:

                    arr = [10, 22, 9, 33, 21, 50, 41, 60]
                

The **Longest Increasing Subsequence (LIS)** is **[10, 22, 33, 50, 60]** (length = 5).

🔹 **Key Points**

• ✅ The elements **must be in increasing order** but **not necessarily contiguous**.
• 📉 The LIS **may not be unique**; multiple valid solutions may exist.

🛠 Solution Approaches

📌 **1. Recursion (Brute Force) – O(2^N) Complexity**

A **recursive solution** checks whether to include an element or exclude it.

                int LIS_Rec(vector& arr, int prev, int index) {
                    if (index == arr.size()) return 0;
            
                    int exclude = LIS_Rec(arr, prev, index + 1);
                    int include = 0;
                    if (prev == -1 || arr[index] > arr[prev]) 
                        include = 1 + LIS_Rec(arr, index, index + 1);
            
                    return max(include, exclude);
                }
                

🔴 **Disadvantage:** This solution is **exponential (O(2^N))** and inefficient for large inputs.

📌 **2. Dynamic Programming (O(N²) Complexity)**

Instead of recomputing results, we store them in a **DP array**.

                int LIS_DP(vector& arr) {
                    int N = arr.size();
                    vector dp(N, 1);
            
                    for (int i = 1; i < N; i++) {
                        for (int j = 0; j < i; j++) {
                            if (arr[i] > arr[j]) 
                                dp[i] = max(dp[i], dp[j] + 1);
                        }
                    }
                    return *max_element(dp.begin(), dp.end());
                }
                

📌 **3. Optimized LIS Using Binary Search (O(N log N))**

We maintain a **sorted array** where each element **replaces** the first larger element found using binary search.

                int LIS_BinarySearch(vector& arr) {
                    vector lis;
                    for (int num : arr) {
                        auto it = lower_bound(lis.begin(), lis.end(), num);
                        if (it == lis.end()) lis.push_back(num);
                        else *it = num;
                    }
                    return lis.size();
                }
                

📌 Printing the LIS Sequence

We store the indices of predecessors to reconstruct the LIS.

                vector printLIS(vector& arr) {
                    int N = arr.size();
                    vector dp(N, 1), parent(N, -1);
                    int maxLen = 0, endIdx = 0;
            
                    for (int i = 1; i < N; i++) {
                        for (int j = 0; j < i; j++) {
                            if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                                dp[i] = dp[j] + 1;
                                parent[i] = j;
                            }
                        }
                        if (dp[i] > maxLen) {
                            maxLen = dp[i];
                            endIdx = i;
                        }
                    }
            
                    vector lis;
                    for (int i = endIdx; i >= 0; i = parent[i]) {
                        lis.push_back(arr[i]);
                        if (parent[i] == -1) break;
                    }
                    reverse(lis.begin(), lis.end());
                    return lis;
                }
                

⏳ Time Complexity Analysis

🌍 Real-World Applications of LIS

• 📈 **Stock Market Analysis** – Finding upward trends.
• 🧬 **Bioinformatics** – DNA sequence alignment.
• 📡 **Data Compression** – Identifying ordered sequences.
• 🔗 **Pattern Recognition** – Analyzing ordered patterns.

🔗 Next Topics

• 🔗 Longest Common Subsequence (LCS)
• 🔍 Binary Search Applications
• 📜 Dynamic Programming Techniques