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.
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5int findNumberOfLIS(int* nums, int numsSize) {
6 if (numsSize == 0) return 0;
7
8 int *lengths = (int*)calloc(numsSize, sizeof(int));
9 int *counts = (int*)calloc(numsSize, sizeof(int));
10 for (int i = 0; i < numsSize; i++) {
11 lengths[i] = 1;
12 counts[i] = 1;
13 }
14
15 int maxLen = 0, result = 0;
16
17 for (int i = 0; i < numsSize; i++) {
18 for (int j = 0; j < i; j++) {
19 if (nums[i] > nums[j]) {
20 if (lengths[j] + 1 > lengths[i]) {
21 lengths[i] = lengths[j] + 1;
22 counts[i] = counts[j];
23 } else if (lengths[j] + 1 == lengths[i]) {
24 counts[i] += counts[j];
25 }
26 }
27 }
28 if (lengths[i] > maxLen) {
29 maxLen = lengths[i];
30 result = counts[i];
31 } else if (lengths[i] == maxLen) {
32 result += counts[i];
33 }
34 }
35
36 free(lengths);
37 free(counts);
38 return result;
39}
40
41int main() {
42 int nums[] = {1, 3, 5, 4, 7};
43 int numsSize = sizeof(nums)/sizeof(nums[0]);
44 printf("%d", findNumberOfLIS(nums, numsSize));
45 return 0;
46}This C function initializes two arrays, lengths and counts, with size corresponding to the input nums. It uses nested loops to compare elements, updating these arrays based on the conditions discussed. The overall length and count logic is surrounded by careful checks to decide whether to extend, begin, or merge subsequences.