Dare2Solve
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.
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.
Initialization:
dp
of size (n+1) x (n+1)
, where n
is the length of the input array nums
. Initialize all elements to 0.Dynamic Programming:
ind
from n-1
to 0
).ind
, iterate through all previous elements (prev
from ind-1
to -1
).(ind, prev)
, compute the length of the LIS ending at ind
and starting after prev
:
len_
to dp[ind + 1][prev + 1]
(the length without including the current element).prev
is -1
(no previous element) or nums[ind] > nums[prev]
(current element can extend the LIS), update len_
to max(len_, 1 + dp[ind + 1][ind + 1])
.dp[ind][prev + 1]
.Result:
dp[0][0]
.O(n^2), where n
is the length of the input array. This is because we have two nested loops iterating through the array.
O(n^2), which is the space required for the 2D dp
array.
class Solution {
public:
int lengthOfLIS(std::vector<int>& nums) {
int n = nums.size();
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(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];
}
};
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]
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
}
}
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];
};