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.
1#include <vector>
2#include <algorithm>
3#include <iostream>
4using namespace std;
5
6int lengthOfLIS(vector<int>& nums) {
7 int n = nums.size();
8 if (n == 0) return 0;
9 vector<int> dp(n, 1);
10 int maxLen = 1;
11 for (int i = 1; i < n; ++i) {
12 for (int j = 0; j < i; ++j) {
13 if (nums[i] > nums[j]) {
14 dp[i] = max(dp[i], dp[j] + 1);
15 }
16 }
17 maxLen = max(maxLen, dp[i]);
18 }
19 return maxLen;
20}
21
22int main() {
23 vector<int> nums = {10,9,2,5,3,7,101,18};
24 cout << lengthOfLIS(nums) << endl;
25 return 0;
26}This solution also uses a dynamic programming array to store the length of the longest subsequence ending at each position. The dp array is iteratively built by comparing elements and updating dp values based on smaller indices.
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.