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 <stdio.h>
2#include <string.h>
3
4int lengthOfLIS(int* nums, int numsSize) {
5 if (numsSize == 0) return 0;
6 int dp[numsSize];
7 memset(dp, 0, sizeof(dp));
8 int maxLen = 1;
9 for (int i = 0; i < numsSize; i++) {
10 dp[i] = 1;
11 for (int j = 0; j < i; j++) {
12 if (nums[i] > nums[j]) {
13 dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
14 }
15 }
16 maxLen = maxLen > dp[i] ? maxLen : dp[i];
17 }
18 return maxLen;
19}
20
21int main() {
22 int nums[] = {10,9,2,5,3,7,101,18};
23 int length = sizeof(nums)/sizeof(nums[0]);
24 printf("%d\n", lengthOfLIS(nums, length));
25 return 0;
26}The code initializes a dp array to store the length of the longest subsequence ending at each index. The outer loop considers each element, and the inner loop checks against elements before the current one to update the dp array. Finally, the maximum length found in the dp array is returned as the result.
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 <vector>
2#include <iostream>
3#include <algorithm>
4using namespace std;
5
6int lengthOfLIS(vector<int>& nums) {
7 vector<int> ends;
8 for (int num : nums) {
9 auto it = lower_bound(ends.begin(), ends.end(), num);
10 if (it == ends.end()) ends.push_back(num);
11 else *it = num;
12 }
13 return ends.size();
14}
15
16int main() {
17 vector<int> nums = {10,9,2,5,3,7,101,18};
18 cout << lengthOfLIS(nums) << endl;
19 return 0;
20}In C++, we utilize the STL function lower_bound to efficiently determine where to insert each element in our 'ends' vector. If an element is greater than all values, a new subsequence is extended; otherwise, it replaces an element to form a better potential subsequence.