Longest Increasing Subsequence (LIS) - CSU083 | Shoolini University

Longest Increasing Subsequence (LIS, Patience Sorting)

2025, February 15

1. Prerequisites

Understanding the Longest Increasing Subsequence (LIS) and its efficient approach using Patience Sorting requires foundational knowledge in:

2. What is the Longest Increasing Subsequence (LIS)?

The Longest Increasing Subsequence (LIS) of an array is the longest subsequence in which all elements are sorted in strictly increasing order.

2.1 Brute Force Approach

A naive recursive approach explores all subsequences and picks the longest increasing one.


def lis_recursive(arr, prev, index):
    if index == len(arr):
        return 0
    taken = 0
    if arr[index] > prev:
        taken = 1 + lis_recursive(arr, arr[index], index + 1)
    not_taken = lis_recursive(arr, prev, index + 1)
    return max(taken, not_taken)

arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_recursive(arr, float('-inf'), 0))  # Exponential time complexity O(2^n)

2.2 Dynamic Programming Approach (O(n²))

Uses a DP table to store LIS ending at each index.


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

arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_dp(arr))  # O(n²) time complexity

2.3 Patience Sorting Approach (O(n log n))

Uses binary search to efficiently place elements into piles.


import bisect

def lis_patience_sort(arr):
    piles = []
    for num in arr:
        pos = bisect.bisect_left(piles, num)
        if pos == len(piles):
            piles.append(num)
        else:
            piles[pos] = num
    return len(piles)

arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_patience_sort(arr))  # O(n log n) time complexity

3. Why Does This Algorithm Exist?

The LIS problem arises in many real-world scenarios where sequences need to be analyzed for increasing trends. Some applications include:

4. When Should You Use It?

Use LIS when you need to find the longest increasing trend in a dataset, particularly in:

5. How Does It Compare to Alternatives?

Method Time Complexity Space Complexity Pros Cons
Brute Force O(2^n) O(n) Easy to implement Exponential time, impractical for large inputs
Dynamic Programming O(n²) O(n) Efficient for moderate input sizes Slower than binary search approach
Patience Sorting O(n log n) O(n) Fastest known approach Does not reconstruct the subsequence

6. Basic Implementation

Here is the implementation of the Longest Increasing Subsequence (LIS) using the Patience Sorting approach in Python.


import bisect

def lis_patience_sort(arr):
    piles = []
    for num in arr:
        pos = bisect.bisect_left(piles, num)
        if pos == len(piles):
            piles.append(num)
        else:
            piles[pos] = num
    return len(piles)

# Example input
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print("Length of LIS:", lis_patience_sort(arr))  
# Expected Output: 4 (LIS could be [2, 3, 7, 18])

7. Dry Run of the Algorithm

Let's dry-run the algorithm with arr = [10, 9, 2, 5, 3, 7, 101, 18] step by step:

7.1 Step-by-Step Execution

Step Number Piles Before Binary Search Index Action Piles After
1 10 [] 0 New pile with 10 [10]
2 9 [10] 0 Replace 10 with 9 [9]
3 2 [9] 0 Replace 9 with 2 [2]
4 5 [2] 1 New pile with 5 [2, 5]
5 3 [2, 5] 1 Replace 5 with 3 [2, 3]
6 7 [2, 3] 2 New pile with 7 [2, 3, 7]
7 101 [2, 3, 7] 3 New pile with 101 [2, 3, 7, 101]
8 18 [2, 3, 7, 101] 3 Replace 101 with 18 [2, 3, 7, 18]

7.2 Final Output

The final number of piles is 4, which is the length of the Longest Increasing Subsequence (LIS). The LIS found is [2, 3, 7, 18].

8. Time & Space Complexity Analysis

8.1 Worst-case Time Complexity

The worst case occurs when each element in the array requires searching and replacing an element in the piles using binary search. The two key operations are:

For an array of size n, each element is processed once, leading to an overall time complexity:

O(n log n)

8.2 Best-case Time Complexity

In the best case, when the array is already sorted in increasing order, each element is appended to the piles, leading to only O(log n) searches per element. The complexity remains:

O(n log n)

8.3 Average-case Time Complexity

On average, elements are placed in piles using binary search, leading to an average complexity of:

O(n log n)

9. Space Complexity Analysis

9.1 Space Consumption with Input Size

10. Understanding the Trade-offs

Factor O(n²) DP Approach O(n log n) Patience Sorting
Time Complexity O(n²) O(n log n)
Space Complexity O(n) O(n)
Ease of Implementation Simple Requires binary search knowledge
Reconstruction of LIS Possible Requires additional tracking
Best Use Case Small input sizes Large input sizes

10.1 When to Use Each Approach?

11. Optimizations & Variants

11.1 Common Optimizations

11.2 Different Versions of the Algorithm

12. Iterative vs. Recursive Implementations

12.1 Recursive Approach (Exponential Time Complexity)

Uses a brute-force recursive strategy, checking every possible subsequence.


def lis_recursive(arr, prev, index):
    if index == len(arr):
        return 0
    taken = 0
    if arr[index] > prev:
        taken = 1 + lis_recursive(arr, arr[index], index + 1)
    not_taken = lis_recursive(arr, prev, index + 1)
    return max(taken, not_taken)

arr = [10, 9, 2, 5, 3, 7, 101, 18]
print("LIS Length:", lis_recursive(arr, float('-inf'), 0))  # O(2^n) complexity

12.2 Iterative Approach (O(n log n) Patience Sorting)

Uses a loop and binary search for efficiency.


import bisect

def lis_iterative(arr):
    piles = []
    for num in arr:
        pos = bisect.bisect_left(piles, num)
        if pos == len(piles):
            piles.append(num)
        else:
            piles[pos] = num
    return len(piles)

print("LIS Length:", lis_iterative(arr))  # O(n log n) complexity

12.3 Efficiency Comparison

Method Time Complexity Space Complexity Performance Best Use Case
Recursive O(2^n) O(n) (Recursive Stack) Very slow for large n Conceptual understanding
Iterative DP O(n²) O(n) Moderate performance Small datasets
Iterative (Patience Sorting) O(n log n) O(n) Best performance Large datasets

13. Edge Cases & Failure Handling

13.1 Common Pitfalls and Edge Cases

14. Test Cases to Verify Correctness

14.1 Sample Test Cases

Using Python's unittest framework to verify correctness:


import unittest
import bisect

def lis_patience_sort(arr):
    piles = []
    for num in arr:
        pos = bisect.bisect_left(piles, num)
        if pos == len(piles):
            piles.append(num)
        else:
            piles[pos] = num
    return len(piles)

class TestLIS(unittest.TestCase):
    def test_empty_array(self):
        self.assertEqual(lis_patience_sort([]), 0)

    def test_single_element(self):
        self.assertEqual(lis_patience_sort([5]), 1)

    def test_all_identical(self):
        self.assertEqual(lis_patience_sort([3, 3, 3, 3]), 1)

    def test_sorted_array(self):
        self.assertEqual(lis_patience_sort([1, 2, 3, 4, 5]), 5)

    def test_reverse_sorted_array(self):
        self.assertEqual(lis_patience_sort([5, 4, 3, 2, 1]), 1)

    def test_mixed_numbers(self):
        self.assertEqual(lis_patience_sort([-5, -1, 0, 2, 3]), 5)

    def test_duplicates(self):
        self.assertEqual(lis_patience_sort([10, 22, 9, 33, 21, 50, 41, 50]), 5)

if __name__ == '__main__':
    unittest.main()

15. Real-World Failure Scenarios

15.1 Handling Real-World Failures

16. Real-World Applications & Industry Use Cases

16.1 Where is LIS Used?

The Longest Increasing Subsequence (LIS) problem appears in various industries and applications:

17. Open-Source Implementations

17.1 Popular Libraries & Projects

Several open-source projects implement LIS for various applications:

17.2 Example - LIS from Python's numpy


import numpy as np

def lis_numpy(arr):
    piles = np.array([])
    for num in arr:
        idx = np.searchsorted(piles, num)
        if idx == len(piles):
            piles = np.append(piles, num)
        else:
            piles[idx] = num
    return len(piles)

arr = [10, 9, 2, 5, 3, 7, 101, 18]
print("LIS Length:", lis_numpy(arr))

18. Project: Real-World LIS Application

18.1 Project: Stock Market Trend Detection

This script identifies the longest increasing trend in stock prices.


import bisect
import matplotlib.pyplot as plt

def lis_stock_trend(prices):
    trends = []
    for price in prices:
        idx = bisect.bisect_left(trends, price)
        if idx == len(trends):
            trends.append(price)
        else:
            trends[idx] = price
    return len(trends), trends

# Example stock prices
stock_prices = [100, 98, 95, 96, 97, 102, 104, 108, 105, 110]
lis_length, trend = lis_stock_trend(stock_prices)

# Plot results
plt.plot(stock_prices, marker="o", linestyle="-", label="Stock Prices")
plt.plot([stock_prices[i] for i in range(len(stock_prices)) if stock_prices[i] in trend], 
         marker="s", linestyle="--", label="LIS Trend")
plt.xlabel("Day")
plt.ylabel("Stock Price")
plt.legend()
plt.title(f"Stock Trend Analysis - LIS Length: {lis_length}")
plt.show()

18.2 Project Extensions

19. Competitive Programming & System Design Integration

19.1 Competitive Programming

The LIS problem appears frequently in coding contests and interviews. Key aspects:

19.2 System Design Applications

In real-world systems, LIS can be applied in:

20. Assignments

20.1 Solve at Least 10 LIS Problems

Practice solving these problems:

  1. Leetcode 300: Longest Increasing Subsequence (Basic LIS)
  2. Leetcode 1048: Longest String Chain (LIS on words)
  3. SPOJ BRIDGE (LIS in coordinate systems)
  4. Leetcode 354: Russian Doll Envelopes (Nested LIS)
  5. Leetcode 646: Maximum Length of Pair Chain (LIS with pairs)
  6. CodeChef DIVSEQ (Divisibility LIS)
  7. Codeforces 1146D: LIS on Subarrays
  8. AtCoder DP Contest N: LIS
  9. Leetcode 329: LIS in a Matrix
  10. Leetcode 673: Number of LIS

20.2 System Design Challenge

Design a system that tracks stock market trends and uses LIS to detect growth trends:

Implement this as a web app using Flask and Matplotlib.

20.3 Timed LIS Implementation

Set a timer and try implementing LIS using:

Improve your speed to implement LIS in under 10 minutes for competitive programming.