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.
1import java.util.*;
2
3public class LongestIncreasingSubsequence {
4 public int lengthOfLIS(int[] nums) {
5 if (nums == null || nums.length == 0)
6 return 0;
7 int n = nums.length;
8 int[] dp = new int[n];
9 Arrays.fill(dp, 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] = Math.max(dp[i], dp[j] + 1);
15 }
16 }
17 maxLen = Math.max(maxLen, dp[i]);
18 }
19 return maxLen;
20 }
21 public static void main(String[] args) {
22 LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
23 int[] nums = {10,9,2,5,3,7,101,18};
24 System.out.println(lis.lengthOfLIS(nums));
25 }
26}The Java solution follows the same logic as C and C++ solutions, using a dp array initialized to 1. It iterates over pairs of elements, updating the array to store the longest subsequence lengths found.
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.