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'))