The next sample exam problem is about finding the longest increasing subsequence of given sequence of integers.
Watch the video lesson about solving the "Sequence of Increasing Elements" problem: https://youtu.be/4ZHRC4usRAM.
A series of n numbers is given: a1, a2, …, an. Calculate the length of the longest increasing sequence of consecutive elements in the series of numbers.
The input data is read from the console. The first line holds an integer n (0 ≤ n ≤ 1000). On the following n lines we read n integers in the range [-1000 … 1000]: a1, a2, …, an.
On the console we must print one number – the length of the longest increasing sequence.
To solve this problem, we need to think in a bit more algorithmic way. A sequence of numbers is given to us, and we need to check whether each subsequent one will be larger than the previous one, and if so, we count how long is the sequence in which this condition is fulfilled. Then we have to find which sequence of these is the longest one. To do this, let's create some variables that we will use during solving the problem.
n is the count of numbers we get from the console. In
countCurrentLongest we will keep the number of elements in the increasing sequence we are currently counting. For example, in the sequence: 5, 6, 1, 2, 3
countCurrentLongest will be 2 when we reach the second element of the counting (5, 6, 1, 2, 3) and will become 3 when we reach the last element (5, 6, 1, 2, 3), because the increasing row 1, 2, 3 has 3 elements. We will use
countLongest to keep the longest increasing sequence. The other variables are
a – the number we are currently in, and
aPrev – the previous number which we will compare with
a to see if the row is growing.
We begin to run the numbers and check if the present number
a is larger than the previous
aPrev one. If this is true, then the row is growing and we need to increase its number by 1. This is stored in the variable that tracks the length of the sequence we are currently in –
countCurrentLongest. If the number
a is not greater than the previous one, it means that a new sequence starts and we have to start the count from 1. Finally, after all the checks are done,
aPrev becomes the number we are currently using and we start the loop from the beginning with the next entered
Here is a sample implementation of the algorithm described:
What remains is to see which of all sequences is the longest one. We will do this by checking in the loop if the sequence we are currently in has become longer than the longest one by now. The whole loop will look like this:
Finally, we print the length of the longest sequence found.
Test your solution here: https://judge.softuni.org/Contests/Practice/Index/516#7.