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.
1class Solution:
2 def lengthOfLIS(self, nums):
3 if not nums:
4 return 0
5 dp = [1] * len(nums)
6 max_len = 1
7 for i in range(1, len(nums)):
8 for j in range(i):
9 if nums[i] > nums[j]:
10 dp[i] = max(dp[i], dp[j] + 1)
11 max_len = max(max_len, dp[i])
12 return max_len
13
14# Example usage:
15nums = [10,9,2,5,3,7,101,18]
16sol = Solution()
17print(sol.lengthOfLIS(nums))In Python, we use a list comprehension to initialize the dp array, then apply the nested loops to update the dp as in other examples.
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).
1import java.util.*;
2
3public class LongestIncreasingSubsequence {
4 public int lengthOfLIS(int[] nums) {
5 if (nums == null || nums.length == 0)
6 return 0;
7 List<Integer> ends = new ArrayList<>();
8 for (int num : nums) {
9 int pos = Collections.binarySearch(ends, num);
10 if (pos < 0) pos = -(pos + 1);
11 if (pos < ends.size()) {
12 ends.set(pos, num);
13 } else {
14 ends.add(num);
15 }
16 }
17 return ends.size();
18 }
19 public static void main(String[] args) {
20 LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
21 int[] nums = {10,9,2,5,3,7,101,18};
22 System.out.println(lis.lengthOfLIS(nums));
23 }
24}Java's Collections.binarySearch is used to find the position to insert each element in the ends list. The position determines whether to extend or replace an element in the list.