INCSEQ - Editorial

[Practice]: (Contest Page | CodeChef)
Author: (codechefnitj | CodeChef User Profile for Codechef NITJ Chapter | CodeChef)
Editorialist: (albus123456 | CodeChef User Profile for anonymous | CodeChef)


Arrays, loops, if -else condition


You are given the heights of the students of a class consisting of n students. Your task is to find the maximum length of an increasing subarray of the given array.
A subarray is the sequence of consecutive elements of the array. Subarray is called increasing if each element of this subarray is strictly greater than the previous.


Next element of an Increasing subarray is greater than previous element. So just comparing consecutive elements. Length of array is <= 10^5 , So a single loop can be used to iterate. (No TLE issue)


Our main task is to iterate over elements over array and check condition for increasing subarray at every point. Since we compare element with its consecutive next element so we have to iterate only till (n-2) (so that it doesn’t go out of bounds and use garbage value) . Our main task is to find that for maximum how many times this condition (that next element is greater than this element) is satisfied . So we keep an variable we keeps account of number of times this condition is satisfied consecutively.[this variable has to be initialized to 1 ,since a single element always satisfies increasing subarray’s condition].
We will also have to keep a variable which stores maximum value of variable (because we have to find maximum length).
We start through the loop , if element satisfies condition increase the count (variable) , otherwise it will enter else statement .It will check the maximum of all the counts (variable) we have encountered till then by using max function. In else statement we have to re initialize value of count to 1 because after it the process starts again (of checking the condition) from next element.
After the loop ends we have to check maximum condition again. Because suppose a case that in last iteration loop satisfies if condition and does not enter else block. So in that case maximum checking is missed.


Time complexity of single for loop is O(n) . Inside it we check maximum of count everytime else block is entered . But it’s time complexity is O(1) because it uses basic if -else principle. So overall time complexity : O(n)


(Solution: 50403543 | CodeChef)

Every suggestion is welcomed with open heart :smile:
Like if it made you understand the concept and problem :+1: