Sponsored
Sponsored
This approach utilizes two arrays to track the length of the longest increasing subsequence ending at each index and the count of such subsequences. The first array, lengths, will store the length of L.I.S. ending at each position, and the second array, counts, will store how many times such a subsequence appears. We iterate through each possible pair of indices to update these arrays accordingly.
Time Complexity: O(n^2) where n is the number of elements in the input array.
Space Complexity: O(n) used for the lengths and counts arrays.
1using System;
2
3public class Solution {
4 public int FindNumberOfLIS(int[] nums) {
5 int n = nums.Length;
6 if (n == 0) return 0;
7
8 int[] lengths = new int[n];
9 int[] counts = new int[n];
10 Array.Fill(lengths, 1);
11 Array.Fill(counts, 1);
12
13 int maxLen = 0, result = 0;
14
15 for (int i = 0; i < n; i++) {
16 for (int j = 0; j < i; j++) {
17 if (nums[i] > nums[j]) {
18 if (lengths[j] + 1 > lengths[i]) {
19 lengths[i] = lengths[j] + 1;
20 counts[i] = counts[j];
21 } else if (lengths[j] + 1 == lengths[i]) {
22 counts[i] += counts[j];
23 }
24 }
25 }
26 if (lengths[i] > maxLen) {
27 maxLen = lengths[i];
28 result = counts[i];
29 } else if (lengths[i] == maxLen) {
30 result += counts[i];
31 }
32 }
33
34 return result;
35 }
36
37 public static void Main(string[] args) {
38 var nums = new int[] {1, 3, 5, 4, 7};
39 Solution sol = new Solution();
40 Console.WriteLine(sol.FindNumberOfLIS(nums));
41 }
42}This C# implementation leverages methods like Array.Fill() to initialize lengths and counts efficiently. C# elegantly handles both loops and array manipulations to maintain clear logic and determinism