Sponsored
Sponsored
This approach involves iterating through the array while maintaining a variable to track the length of the current continuous increasing subsequence. As we encounter each element, we check if it is larger than the previous one to decide if we should continue the current subsequence or start a new one. We also maintain a global maximum to store the maximum length found during our iteration.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as we use a constant amount of space.
1#include <stdio.h>
2
3int findLengthOfLCIS(int* nums, int numsSize) {
4 if (numsSize == 0) return 0;
5 int maxLen = 1, currLen = 1;
6
7 for (int i = 1; i < numsSize; i++) {
8 if (nums[i] > nums[i - 1]) {
9 currLen++;
10 if (currLen > maxLen) {
11 maxLen = currLen;
12 }
13 } else {
14 currLen = 1;
15 }
16 }
17 return maxLen;
18}
19
20int main() {
21 int nums[] = {1, 3, 5, 4, 7};
22 int length = sizeof(nums) / sizeof(nums[0]);
23 printf("%d\n", findLengthOfLCIS(nums, length));
24 return 0;
25}The function findLengthOfLCIS accepts an array and its size. We initialize maxLen and currLen to 1. We iterate through the array, and whenever the current element is greater than the previous one, we increase currLen. If currLen exceeds maxLen, we update maxLen. When the sequence breaks, we reset currLen to 1.
The greedy approach leverages a single pass through the array to determine the maximum length of an increasing subsequence. This method is optimal because it immediately processes each element only once, updating the sequence lengths on the fly, and computing the maximum without revisiting any part of the array.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as no additional space other than variables is utilized.
1
class LCIS {
public static int FindLengthOfLCIS(int[] nums) {
int maxLen = 0, currLen = 0;
for (int i = 0; i < nums.Length; i++) {
if (i == 0 || nums[i] > nums[i - 1]) {
currLen++;
maxLen = Math.Max(maxLen, currLen);
} else {
currLen = 1;
}
}
return maxLen;
}
static void Main() {
int[] nums = {1, 3, 5, 4, 7};
Console.WriteLine(FindLengthOfLCIS(nums));
}
}Illustrating the inherent nature of greedy methods, this C# solution works by dynamically updating variables without looking backwards or apart from current sequence tracking elements optimally.