Longest Increasing Subsequence

Building on our previous discussions of Dynamic Programming, let’s explore the Longest Increasing Subsequence (LIS) problem. Given an array of integers, we need to find the longest sequence where each element is greater than its previous elements.

Let’s visualize how LIS works with an example array:

flowchart TD
    subgraph "Array Processing"
        direction TB
        
        A["Input Array: [10, 22, 9, 33, 21, 50, 41, 60, 80]"]
        
        subgraph "DP Matrix Construction"
            direction TB
            
            M1["Initialize dp array:
            [1, 1, 1, 1, 1, 1, 1, 1, 1]"]
            
            M2["After processing:
            [1, 2, 1, 3, 2, 4, 3, 5, 6]"]
            
            M3["Final Result:
            LIS Length = 6
            Sequence: [10, 22, 33, 50, 60, 80]"]
        end
        
        A --> M1
        M1 --> M2
        M2 --> M3
    end
    
    style M1 text-align:left
    style M2 text-align:left
    style M3 text-align:left

In the diagram above:

• Each cell represents the length of LIS ending at that position
• Numbers increase when we find a larger number that can extend our current sequence
• The final result [10, 22, 33, 50, 60, 80] comes from tracing back through the highest values

Let’s implement this algorithm using different approaches:

Basic Implementation with Matrix Visualization```python

def lis_basic(arr):
    n = len(arr)
    # Create DP matrix
    dp = [[num] for num in arr]
    
    # Fill the matrix
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j] and len(dp[j]) + 1 > len(dp[i]):
                dp[i] = dp[j] + [arr[i]]
    
    # Find longest sequence
    return max(dp, key=len)
 
# Example usage
arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
sequence = lis_basic(arr)
print(f"LIS: {sequence}")  # Output: [10, 22, 33, 50, 60, 80]

• Clear visualization of DP process
• Stores actual sequences instead of lengths
• Easy to understand and debug
• Uses O(n²) space
• Less efficient for large arrays

This implementation creates a dynamic programming array where each cell contains the actual increasing sequence ending at that position. When we find a larger number that can extend our current sequence, we create a new longer sequence. Optimized Binary Search Implementation```python from bisect import bisect_left

def lis_optimized(arr):
    if not arr:
        return []
        
    # Store smallest tail of each subsequence length
    tails = [arr[0]]
    # Store indices for reconstruction
    indices = {arr[0]: 0}
    # Previous element index for reconstruction
    prev_idx = {0: -1}
    
    for i in range(1, len(arr)):
        if arr[i] < tails[0]:
            tails[0] = arr[i]
            indices[arr[i]] = i
            prev_idx[i] = -1
        elif arr[i] > tails[-1]:
            tails.append(arr[i])
            indices[arr[i]] = len(tails) - 1
            prev_idx[i] = indices[tails[-2]]
        else:
            # Find position to replace
            pos = bisect_left(tails, arr[i])
            tails[pos] = arr[i]
            indices[arr[i]] = pos
            prev_idx[i] = indices[tails[pos-1]]
    
    # Reconstruct sequence
    result = []
    curr_idx = max(prev_idx.keys())
    while curr_idx != -1:
        result.append(arr[curr_idx])
        curr_idx = prev_idx[curr_idx]
        
    return list(reversed(result))
 
# Example usage
arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
sequence = lis_optimized(arr)
print(f"LIS: {sequence}")  # Output: [10, 22, 33, 50, 60, 80]

• Uses O(n) space
• More efficient for large arrays
• Maintains sequence reconstruction
• More complex implementation
• Harder to visualize the DP process

This optimized version uses binary search to find positions efficiently and maintains only the smallest tail element for each subsequence length. It achieves O(n log n) time complexity while reducing space usage significantly.

Time and Space Complexity Analysis

Implementation	Time Complexity	Space Complexity
Basic	O(n²)	O(n²)
Optimized	O(n log n)	O(n)

Common Variations

1. Longest Decreasing Subsequence - Similar approach but looks for decreasing sequences

• Used in stock price analysis

2. Longest Increasing Subsequence with Constraints - Add constraints like minimum gap between elements

• Used in scheduling and resource allocation

3. Multiple Dimensional LIS - Extend to arrays with multiple dimensions

• Used in data analysis and pattern recognition

Best Practices

1. Implementation Guidelines - Always initialize dp array properly

• Consider edge cases (empty arrays)
• Profile performance for large inputs

2. Space Optimization Tips - Store only necessary information

• Consider trade-offs between space and readability
• Use binary search for position finding

3. Sequence Reconstruction - Maintain indices for backtracking

• Handle ties consistently
• Consider bidirectional tracing for optimal solutions

LIS is a classic Dynamic Programming problem that demonstrates both overlapping subproblems and optimal substructure properties 2:0. The solution builds upon smaller subproblems to construct the final sequence efficiently.