300. Longest Increasing Subsequence
Explanation
To solve this problem, we can use dynamic programming with a slightly modified approach to find the longest increasing subsequence. We will create an array dp to store the length of the longest increasing subsequence ending at index i. For each element at index i, we iterate through all previous elements to find the maximum length ending at index i.
The time complexity of this dynamic programming approach is O(n^2), where n is the number of elements in the input array. However, we can optimize this solution to run in O(n log(n)) time complexity using a binary search-based approach.
The optimized algorithm involves maintaining a separate array tails which will store the smallest tail of all increasing subsequences with length i+1. We iterate through the input array and update the tails array based on the current element's value. The length of the longest increasing subsequence will be the length of the tails array.
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] tails = new int[n];
int len = 0;
for (int num : nums) {
int i = 0, j = len;
while (i < j) {
int mid = i + (j - i) / 2;
if (tails[mid] < num) {
i = mid + 1;
} else {
j = mid;
}
}
tails[i] = num;
if (i == len) {
len++;
}
}
return len;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.