This approach uses dynamic programming to solve the problem in O(n^2) time complexity. We maintain a dp array where dp[i] represents the length of the longest increasing subsequence that ends with nums[i]. For each element, we iterate over all previous elements to see if they can be included in the subsequence ending at the current element, and update dp[i] accordingly.
Time Complexity: O(n^2) where n is the length of the input array. Space Complexity: O(n) for storing the dp array.
1function lengthOfLIS(nums) {
2 if (nums.length === 0) return 0;
3 const dp = Array(nums.length).fill(1);
4 let maxLen = 1;
5 for (let i = 1; i < nums.length; i++) {
6 for (let j = 0; j < i; j++) {
7 if (nums[i] > nums[j]) {
8 dp[i] = Math.max(dp[i], dp[j] + 1);
9 }
10 }
11 maxLen = Math.max(maxLen, dp[i]);
12 }
13 return maxLen;
14}
15
16console.log(lengthOfLIS([10,9,2,5,3,7,101,18]));In JavaScript, we use similar logic as other languages to iteratively build the dp array. The max length is calculated and updated through nested conditions.
In this approach, we use a combination of dynamic programming and binary search to solve the problem in O(n log n) time. This is often called the 'patience sorting' technique where we maintain a list, 'ends', to store the smallest ending value of any increasing subsequence with length i+1 in 'ends[i]'. We use binary search to find the position where each element in nums can be placed in 'ends'.
Time Complexity: O(n log n). Space Complexity: O(n).
1#include <stdio.h>
2#include <stdlib.h>
3
4int comparator(const void *a, const void *b) {
5 return (*(int *)a - *(int *)b);
6}
7
8int lowerBound(int *arr, int size, int value) {
9 int low = 0, high = size;
10 while (low < high) {
11 int mid = low + (high - low) / 2;
12 if (arr[mid] < value) {
13 low = mid + 1;
14 } else {
15 high = mid;
16 }
17 }
18 return low;
19}
20
21int lengthOfLIS(int* nums, int numsSize) {
22 if (numsSize == 0) return 0;
23 int* ends = (int*)malloc(numsSize * sizeof(int));
24 int length = 0;
25 for (int i = 0; i < numsSize; ++i) {
26 int pos = lowerBound(ends, length, nums[i]);
27 ends[pos] = nums[i];
28 if (pos == length) {
29 length++;
30 }
31 }
32 free(ends);
33 return length;
34}
35
36int main() {
37 int nums[] = {10,9,2,5,3,7,101,18};
38 int length = sizeof(nums)/sizeof(nums[0]);
39 printf("%d\n", lengthOfLIS(nums, length));
40 return 0;
41}This C solution uses a lowerBound function which acts similarly to std::lower_bound in C++. It finds the position to insert (or replace) each element of nums in the 'ends' list, effectively forming the required subsequences.