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.
1using System;
2
3public class Solution {
4 public int LengthOfLIS(int[] nums) {
5 if (nums == null || nums.Length == 0) return 0;
6 int n = nums.Length;
7 int[] dp = new int[n];
8 Array.Fill(dp, 1);
9 int maxLen = 1;
10 for (int i = 1; i < n; i++) {
11 for (int j = 0; j < i; j++) {
12 if (nums[i] > nums[j]) {
13 dp[i] = Math.Max(dp[i], dp[j] + 1);
14 }
15 }
16 maxLen = Math.Max(maxLen, dp[i]);
17 }
18 return maxLen;
19 }
20 public static void Main() {
21 int[] nums = {10,9,2,5,3,7,101,18};
22 Solution sol = new Solution();
23 Console.WriteLine(sol.LengthOfLIS(nums));
24 }
25}The C# solution mimics other language solutions with dynamic programming, utilizing nested loops to progressively build up the dp array values.
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).
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int LengthOfLIS(int[] nums) {
6 List<int> ends = new List<int>();
7 foreach (var num in nums) {
8 int idx = ends.BinarySearch(num);
9 if (idx < 0) idx = ~idx;
10 if (idx < ends.Count) {
11 ends[idx] = num;
12 } else {
13 ends.Add(num);
14 }
15 }
16 return ends.Count;
17 }
18 public static void Main() {
19 int[] nums = {10,9,2,5,3,7,101,18};
20 Solution sol = new Solution();
21 Console.WriteLine(sol.LengthOfLIS(nums));
22 }
23}The C# solution uses List's BinarySearch method to find the insertion point of each element efficiently, ensuring we maintain optimal subsequence structures.