
Description
The problem is to find the length of the longest increasing subsequence (LIS) in a given array of integers nums
. An increasing subsequence is a subsequence that appears in the same relative order as the original array but not necessarily contiguously and all elements of the subsequence are in strictly increasing order.
Intuition
The intuition behind solving the LIS problem is to use dynamic programming to break down the problem into simpler subproblems. By keeping track of the longest increasing subsequences ending at each index and building up the solution incrementally, we can efficiently determine the overall LIS length. The key is to compare each element with all previous elements and decide whether to include it in the increasing subsequence or not.
Approach
- Initialization:
- Create a 2D array
dp
of size(n+1) x (n+1)
, wheren
is the length of the input arraynums
. Initialize all elements to 0. - Dynamic Programming:
- Iterate through the array from the end to the beginning (
ind
fromn-1
to0
). - For each element at indexind
, iterate through all previous elements (prev
fromind-1
to-1
). - For each pair(ind, prev)
, compute the length of the LIS ending atind
and starting afterprev
: - Initializelen_
todp[ind + 1][prev + 1]
(the length without including the current element). - Ifprev
is-1
(no previous element) ornums[ind] > nums[prev]
(current element can extend the LIS), updatelen_
tomax(len_, 1 + dp[ind + 1][ind + 1])
. - Store the computed length indp[ind][prev + 1]
. - Result:
- The length of the longest increasing subsequence is stored in
dp[0][0]
.
Complexity
Time Complexity:
O(n^2), where n
is the length of the input array. This is because we have two nested loops iterating through the array.
Space Complexity:
O(n^2), which is the space required for the 2D dp
array.
Code
C++
class Solution {
public:
int lengthOfLIS(std::vector& nums) {
int n = nums.size();
std::vector> dp(n + 1, std::vector(n + 1, 0));
for (int ind = n - 1; ind >= 0; ind--) {
for (int prev = ind - 1; prev >= -1; prev--) {
int len = dp[ind + 1][prev + 1];
if (prev == -1 || nums[ind] > nums[prev]) {
len = std::max(len, 1 + dp[ind + 1][ind + 1]);
}
dp[ind][prev + 1] = len;
}
}
return dp[0][0];
}
};
Python
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [[0] * (n + 1) for _ in range(n + 1)]
for ind in range(n - 1, -1, -1):
for prev in range(ind - 1, -2, -1):
len_ = dp[ind + 1][prev + 1]
if prev == -1 or nums[ind] > nums[prev]:
len_ = max(len_, 1 + dp[ind + 1][ind + 1])
dp[ind][prev + 1] = len_
return dp[0][0]
Java
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[][] dp = new int[n + 1][n + 1];
for (int ind = n - 1; ind >= 0; ind--) {
for (int prev = ind - 1; prev >= -1; prev--) {
int len = dp[ind + 1][prev + 1];
if (prev == -1 || nums[ind] > nums[prev]) {
len = Math.max(len, 1 + dp[ind + 1][ind + 1]);
}
dp[ind][prev + 1] = len;
}
}
return dp[0][0];
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println(solution.lengthOfLIS(nums)); // Output: 4
}
}
JavaScript
var lengthOfLIS = function(nums) {
let dp = Array.from({ length: nums.length+1 }, () => Array(nums.length+1).fill(0));
for (let ind = nums.length-1; ind >= 0; ind--) {
for (let prev = ind-1; prev >= -1; prev--) {
let len = dp[ind+1][prev+1];
if(prev == -1 || nums[ind] > nums[prev]){
len = Math.max(len, 1+ dp[ind+1][ind+1]);
}
dp[ind][prev+1] = len;
}
}
return dp[0][0];
};