AntInLoop

Longest Increasing Subsequence (LIS) Code Implementations

Complete Longest Increasing Subsequence (LIS) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Longest Increasing Subsequence (LIS) Guide ยท Launch Interactive Visualizer

C++ Implementation

// Longest Increasing Subsequence Implementation in C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

class LongestIncreasingSubsequence {
public:
    static int longestIncreasingSubsequence(const std::vector<int>& nums) {
        if (nums.empty()) return 0;
        
        std::vector<int> dp(nums.size(), 1);
        
        for (size_t i = 1; i < nums.size(); i++) {
            for (size_t j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = std::max(dp[i], dp[j] + 1);
                }
            }
        }
        
        return *std::max_element(dp.begin(), dp.end());
    }
    
    // LIS with O(n log n) time complexity using binary search
    static int longestIncreasingSubsequenceOptimized(const std::vector<int>& nums) {
        if (nums.empty()) return 0;
        
        std::vector<int> tails;
        tails.push_back(nums[0]);
        
        for (size_t i = 1; i < nums.size(); i++) {
            if (nums[i] > tails.back()) {
                tails.push_back(nums[i]);
            } else {
                auto pos = std::lower_bound(tails.begin(), tails.end(), nums[i]);
                *pos = nums[i];
            }
        }
        
        return tails.size();
    }
    
    // LIS with subsequence reconstruction
    struct LISResult {
        int length;
        std::vector<int> subsequence;
        
        LISResult(int len, const std::vector<int>& sub) : length(len), subsequence(sub) {}
    };
    
    static LISResult longestIncreasingSubsequenceWithArray(const std::vector<int>& nums) {
        if (nums.empty()) {
            return LISResult(0, {});
        }
        
        std::vector<int> dp(nums.size(), 1);
        std::vector<int> prev(nums.size(), -1);
        
        for (size_t i = 1; i < nums.size(); i++) {
            for (size_t j = 0; j < i; j++) {
                if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
        }
        
        // Find the end of the longest subsequence
        size_t maxIndex = 0;
        for (size_t i = 1; i < nums.size(); i++) {
            if (dp[i] > dp[maxIndex]) {
                maxIndex = i;
            }
        }
        
        // Reconstruct the subsequence
        std::vector<int> subsequence;
        int current = maxIndex;
        while (current != -1) {
            subsequence.insert(subsequence.begin(), nums[current]);
            current = prev[current];
        }
        
        return LISResult(dp[maxIndex], subsequence);
    }
    
    // LIS with O(n log n) and subsequence reconstruction
    static LISResult longestIncreasingSubsequenceOptimizedWithArray(const std::vector<int>& nums) {
        if (nums.empty()) {
            return LISResult(0, {});
        }
        
        std::vector<int> tails;
        std::vector<int> indices;
        std::vector<int> prev(nums.size(), -1);
        
        tails.push_back(nums[0]);
        indices.push_back(0);
        
        for (size_t i = 1; i < nums.size(); i++) {
            if (nums[i] > tails.back()) {
                prev[i] = indices.back();
                tails.push_back(nums[i]);
                indices.push_back(i);
            } else {
                auto pos = std::lower_bound(tails.begin(), tails.end(), nums[i]);
                size_t index = pos - tails.begin();
                tails[index] = nums[i];
                indices[index] = i;
                if (index > 0) {
                    prev[i] = indices[index - 1];
                }
            }
        }
        
        // Reconstruct the subsequence
        std::vector<int> subsequence;
        int current = indices.back();
        while (current != -1) {
            subsequence.insert(subsequence.begin(), nums[current]);
            current = prev[current];
        }
        
        return LISResult(tails.size(), subsequence);
    }
    
    // LIS with strict increasing (no duplicates)
    static int longestStrictlyIncreasingSubsequence(const std::vector<int>& nums) {
        if (nums.empty()) return 0;
        
        std::vector<int> tails;
        tails.push_back(nums[0]);
        
        for (size_t i = 1; i < nums.size(); i++) {
            if (nums[i] > tails.back()) {
                tails.push_back(nums[i]);
            } else {
                auto pos = std::lower_bound(tails.begin(), tails.end(), nums[i]);
                *pos = nums[i];
            }
        }
        
        return tails.size();
    }
    
    // LIS with non-decreasing (allowing duplicates)
    static int longestNonDecreasingSubsequence(const std::vector<int>& nums) {
        if (nums.empty()) return 0;
        
        std::vector<int> tails;
        tails.push_back(nums[0]);
        
        for (size_t i = 1; i < nums.size(); i++) {
            if (nums[i] >= tails.back()) {
                tails.push_back(nums[i]);
            } else {
                auto pos = std::upper_bound(tails.begin(), tails.end(), nums[i]);
                *pos = nums[i];
            }
        }
        
        return tails.size();
    }
    
    // LIS with memoization (top-down approach)
    static int longestIncreasingSubsequenceMemo(const std::vector<int>& nums) {
        if (nums.empty()) return 0;
        
        std::unordered_map<std::string, int> memo;
        
        return solveMemo(nums, 0, INT_MIN, memo);
    }
    
private:
    static int solveMemo(const std::vector<int>& nums, int index, int prevVal, 
                        std::unordered_map<std::string, int>& memo) {
        if (index == nums.size()) {
            return 0;
        }
        
        std::string key = std::to_string(index) + "," + std::to_string(prevVal);
        if (memo.find(key) != memo.end()) {
            return memo[key];
        }
        
        // Don't include current element
        int result = solveMemo(nums, index + 1, prevVal, memo);
        
        // Include current element if it's greater than previous
        if (nums[index] > prevVal) {
            result = std::max(result, 1 + solveMemo(nums, index + 1, nums[index], memo));
        }
        
        memo[key] = result;
        return result;
    }
};

JAVA Implementation

// Longest Increasing Subsequence Implementation in Java
public class LongestIncreasingSubsequence {
    public static int longestIncreasingSubsequence(int[] nums) {
        if (nums.length == 0) return 0;
        
        int[] dp = new int[nums.length];
        java.util.Arrays.fill(dp, 1);
        
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        
        int maxLength = 0;
        for (int length : dp) {
            maxLength = Math.max(maxLength, length);
        }
        
        return maxLength;
    }
    
    // LIS with O(n log n) time complexity using binary search
    public static int longestIncreasingSubsequenceOptimized(int[] nums) {
        if (nums.length == 0) return 0;
        
        java.util.List<Integer> tails = new java.util.ArrayList<>();
        tails.add(nums[0]);
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > tails.get(tails.size() - 1)) {
                tails.add(nums[i]);
            } else {
                int pos = binarySearch(tails, nums[i]);
                tails.set(pos, nums[i]);
            }
        }
        
        return tails.size();
    }
    
    // Binary search helper function
    private static int binarySearch(java.util.List<Integer> arr, int target) {
        int left = 0;
        int right = arr.size() - 1;
        
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
    
    // LIS with subsequence reconstruction
    public static class LISResult {
        public int length;
        public int[] subsequence;
        
        public LISResult(int length, int[] subsequence) {
            this.length = length;
            this.subsequence = subsequence;
        }
    }
    
    public static LISResult longestIncreasingSubsequenceWithArray(int[] nums) {
        if (nums.length == 0) {
            return new LISResult(0, new int[0]);
        }
        
        int[] dp = new int[nums.length];
        int[] prev = new int[nums.length];
        java.util.Arrays.fill(dp, 1);
        java.util.Arrays.fill(prev, -1);
        
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
        }
        
        // Find the end of the longest subsequence
        int maxIndex = 0;
        for (int i = 1; i < nums.length; i++) {
            if (dp[i] > dp[maxIndex]) {
                maxIndex = i;
            }
        }
        
        // Reconstruct the subsequence
        java.util.List<Integer> subsequence = new java.util.ArrayList<>();
        int current = maxIndex;
        while (current != -1) {
            subsequence.add(0, nums[current]);
            current = prev[current];
        }
        
        int[] result = subsequence.stream().mapToInt(Integer::intValue).toArray();
        return new LISResult(dp[maxIndex], result);
    }
    
    // LIS with O(n log n) and subsequence reconstruction
    public static LISResult longestIncreasingSubsequenceOptimizedWithArray(int[] nums) {
        if (nums.length == 0) {
            return new LISResult(0, new int[0]);
        }
        
        java.util.List<Integer> tails = new java.util.ArrayList<>();
        java.util.List<Integer> indices = new java.util.ArrayList<>();
        int[] prev = new int[nums.length];
        
        tails.add(nums[0]);
        indices.add(0);
        java.util.Arrays.fill(prev, -1);
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > tails.get(tails.size() - 1)) {
                prev[i] = indices.get(indices.size() - 1);
                tails.add(nums[i]);
                indices.add(i);
            } else {
                int pos = binarySearch(tails, nums[i]);
                tails.set(pos, nums[i]);
                indices.set(pos, i);
                if (pos > 0) {
                    prev[i] = indices.get(pos - 1);
                }
            }
        }
        
        // Reconstruct the subsequence
        java.util.List<Integer> subsequence = new java.util.ArrayList<>();
        int current = indices.get(indices.size() - 1);
        while (current != -1) {
            subsequence.add(0, nums[current]);
            current = prev[current];
        }
        
        int[] result = subsequence.stream().mapToInt(Integer::intValue).toArray();
        return new LISResult(tails.size(), result);
    }
    
    // LIS with strict increasing (no duplicates)
    public static int longestStrictlyIncreasingSubsequence(int[] nums) {
        if (nums.length == 0) return 0;
        
        java.util.List<Integer> tails = new java.util.ArrayList<>();
        tails.add(nums[0]);
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > tails.get(tails.size() - 1)) {
                tails.add(nums[i]);
            } else {
                int pos = binarySearchStrict(tails, nums[i]);
                tails.set(pos, nums[i]);
            }
        }
        
        return tails.size();
    }
    
    // Binary search for strict increasing
    private static int binarySearchStrict(java.util.List<Integer> arr, int target) {
        int left = 0;
        int right = arr.size() - 1;
        
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
    
    // LIS with non-decreasing (allowing duplicates)
    public static int longestNonDecreasingSubsequence(int[] nums) {
        if (nums.length == 0) return 0;
        
        java.util.List<Integer> tails = new java.util.ArrayList<>();
        tails.add(nums[0]);
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= tails.get(tails.size() - 1)) {
                tails.add(nums[i]);
            } else {
                int pos = binarySearchNonDecreasing(tails, nums[i]);
                tails.set(pos, nums[i]);
            }
        }
        
        return tails.size();
    }
    
    // Binary search for non-decreasing
    private static int binarySearchNonDecreasing(java.util.List<Integer> arr, int target) {
        int left = 0;
        int right = arr.size() - 1;
        
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr.get(mid) <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
    
    // LIS with memoization (top-down approach)
    public static int longestIncreasingSubsequenceMemo(int[] nums) {
        if (nums.length == 0) return 0;
        
        java.util.Map<String, Integer> memo = new java.util.HashMap<>();
        
        return solveMemo(nums, 0, Integer.MIN_VALUE, memo);
    }
    
private:
    static int solveMemo(const std::vector<int>& nums, int index, int prevVal, 
                        std::unordered_map<std::string, int>& memo) {
        if (index == nums.size()) {
            return 0;
        }
        
        std::string key = std::to_string(index) + "," + std::to_string(prevVal);
        if (memo.find(key) != memo.end()) {
            return memo[key];
        }
        
        // Don't include current element
        int result = solveMemo(nums, index + 1, prevVal, memo);
        
        // Include current element if it's greater than previous
        if (nums[index] > prevVal) {
            result = std::max(result, 1 + solveMemo(nums, index + 1, nums[index], memo));
        }
        
        memo[key] = result;
        return result;
    }
};

JAVASCRIPT Implementation

// Longest Increasing Subsequence Implementation in JavaScript
function longestIncreasingSubsequence(nums) {
  if (nums.length === 0) return 0;
  
  const dp = new Array(nums.length).fill(1);
  
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  
  return Math.max(...dp);
}

// LIS with O(n log n) time complexity using binary search
function longestIncreasingSubsequenceOptimized(nums) {
  if (nums.length === 0) return 0;
  
  const tails = [nums[0]];
  
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > tails[tails.length - 1]) {
      tails.push(nums[i]);
    } else {
      // Find the position to replace using binary search
      const pos = binarySearch(tails, nums[i]);
      tails[pos] = nums[i];
    }
  }
  
  return tails.length;
}

// Binary search helper function
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  
  return left;
}

// LIS with subsequence reconstruction
function longestIncreasingSubsequenceWithArray(nums) {
  if (nums.length === 0) return { length: 0, subsequence: [] };
  
  const dp = new Array(nums.length).fill(1);
  const prev = new Array(nums.length).fill(-1);
  
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
        prev[i] = j;
      }
    }
  }
  
  // Find the end of the longest subsequence
  let maxIndex = 0;
  for (let i = 1; i < nums.length; i++) {
    if (dp[i] > dp[maxIndex]) {
      maxIndex = i;
    }
  }
  
  // Reconstruct the subsequence
  const subsequence = [];
  let current = maxIndex;
  while (current !== -1) {
    subsequence.unshift(nums[current]);
    current = prev[current];
  }
  
  return {
    length: dp[maxIndex],
    subsequence: subsequence
  };
}

// LIS with O(n log n) and subsequence reconstruction
function longestIncreasingSubsequenceOptimizedWithArray(nums) {
  if (nums.length === 0) return { length: 0, subsequence: [] };
  
  const tails = [nums[0]];
  const indices = [0];
  const prev = new Array(nums.length).fill(-1);
  
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > tails[tails.length - 1]) {
      prev[i] = indices[indices.length - 1];
      tails.push(nums[i]);
      indices.push(i);
    } else {
      const pos = binarySearch(tails, nums[i]);
      tails[pos] = nums[i];
      indices[pos] = i;
      if (pos > 0) {
        prev[i] = indices[pos - 1];
      }
    }
  }
  
  // Reconstruct the subsequence
  const subsequence = [];
  let current = indices[indices.length - 1];
  while (current !== -1) {
    subsequence.unshift(nums[current]);
    current = prev[current];
  }
  
  return {
    length: tails.length,
    subsequence: subsequence
  };
}

// LIS with strict increasing (no duplicates)
function longestStrictlyIncreasingSubsequence(nums) {
  if (nums.length === 0) return 0;
  
  const tails = [nums[0]];
  
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > tails[tails.length - 1]) {
      tails.push(nums[i]);
    } else {
      const pos = binarySearchStrict(tails, nums[i]);
      tails[pos] = nums[i];
    }
  }
  
  return tails.length;
}

// Binary search for strict increasing
function binarySearchStrict(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  
  return left;
}

// LIS with non-decreasing (allowing duplicates)
function longestNonDecreasingSubsequence(nums) {
  if (nums.length === 0) return 0;
  
  const tails = [nums[0]];
  
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] >= tails[tails.length - 1]) {
      tails.push(nums[i]);
    } else {
      const pos = binarySearchNonDecreasing(tails, nums[i]);
      tails[pos] = nums[i];
    }
  }
  
  return tails.length;
}

// Binary search for non-decreasing
function binarySearchNonDecreasing(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] <= target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  
  return left;
}

PYTHON Implementation

# Longest Increasing Subsequence Implementation in Python
def longest_increasing_subsequence(nums):
    if not nums:
        return 0
    
    dp = [1] * len(nums)
    
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

# LIS with O(n log n) time complexity using binary search
def longest_increasing_subsequence_optimized(nums):
    if not nums:
        return 0
    
    tails = [nums[0]]
    
    for i in range(1, len(nums)):
        if nums[i] > tails[-1]:
            tails.append(nums[i])
        else:
            # Find the position to replace using binary search
            pos = binary_search(tails, nums[i])
            tails[pos] = nums[i]
    
    return len(tails)

# Binary search helper function
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left

# LIS with subsequence reconstruction
def longest_increasing_subsequence_with_array(nums):
    if not nums:
        return {'length': 0, 'subsequence': []}
    
    dp = [1] * len(nums)
    prev = [-1] * len(nums)
    
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j
    
    # Find the end of the longest subsequence
    max_index = 0
    for i in range(1, len(nums)):
        if dp[i] > dp[max_index]:
            max_index = i
    
    # Reconstruct the subsequence
    subsequence = []
    current = max_index
    while current != -1:
        subsequence.insert(0, nums[current])
        current = prev[current]
    
    return {
        'length': dp[max_index],
        'subsequence': subsequence
    }

# LIS with O(n log n) and subsequence reconstruction
def longest_increasing_subsequence_optimized_with_array(nums):
    if not nums:
        return {'length': 0, 'subsequence': []}
    
    tails = [nums[0]]
    indices = [0]
    prev = [-1] * len(nums)
    
    for i in range(1, len(nums)):
        if nums[i] > tails[-1]:
            prev[i] = indices[-1]
            tails.append(nums[i])
            indices.append(i)
        else:
            pos = binary_search(tails, nums[i])
            tails[pos] = nums[i]
            indices[pos] = i
            if pos > 0:
                prev[i] = indices[pos - 1]
    
    # Reconstruct the subsequence
    subsequence = []
    current = indices[-1]
    while current != -1:
        subsequence.insert(0, nums[current])
        current = prev[current]
    
    return {
        'length': len(tails),
        'subsequence': subsequence
    }

# LIS with strict increasing (no duplicates)
def longest_strictly_increasing_subsequence(nums):
    if not nums:
        return 0
    
    tails = [nums[0]]
    
    for i in range(1, len(nums)):
        if nums[i] > tails[-1]:
            tails.append(nums[i])
        else:
            pos = binary_search_strict(tails, nums[i])
            tails[pos] = nums[i]
    
    return len(tails)

# Binary search for strict increasing
def binary_search_strict(arr, target):
    left, right = 0, len(arr) - 1
    
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left

# LIS with non-decreasing (allowing duplicates)
def longest_non_decreasing_subsequence(nums):
    if not nums:
        return 0
    
    tails = [nums[0]]
    
    for i in range(1, len(nums)):
        if nums[i] >= tails[-1]:
            tails.append(nums[i])
        else:
            pos = binary_search_non_decreasing(tails, nums[i])
            tails[pos] = nums[i]
    
    return len(tails)

# Binary search for non-decreasing
def binary_search_non_decreasing(arr, target):
    left, right = 0, len(arr) - 1
    
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    
    return left

# LIS with memoization (top-down approach)
def longest_increasing_subsequence_memo(nums):
    if not nums:
        return 0
    
    memo = {}
    
    def solve(index, prev_val):
        if index == len(nums):
            return 0
        
        key = (index, prev_val)
        if key in memo:
            return memo[key]
        
        # Don't include current element
        result = solve(index + 1, prev_val)
        
        # Include current element if it's greater than previous
        if nums[index] > prev_val:
            result = max(result, 1 + solve(index + 1, nums[index]))
        
        memo[key] = result
        return result
    
    return solve(0, float('-inf'))