Ninja Training

Moderate

0/80

Average time to solve is 30m

Contributed by

10 upvotes

Problem statement

Ninja is training very hard for the coming Ninja’s Olympics. First, he is practicing for jumps, while training he is jumping from one building to another.

There are ‘N’ numbers of building in the city of Ninjas, and Ninja can jump from one building to the next only if the difference between the heights of the buildings is of opposite sign or say alternate from the difference of heights of building from his previous jump.

For Example:

[1, 3, 2, 5, 4] is the possible building heights that Ninja can course on, As the difference of consecutive building heights is [ 2, -1, 3, -1] which is alternatively positive and negative. 

Whereas [1, 2, 3, 4, 5] is not a possible course as the difference array is[ 1, 2, 3, 4] which is not alternatively positive and negative.

So you are given an integer ‘N’ and an array ‘ARR’ of size ‘N’. Find the maximum times Ninja can jump to make his training most efficient.

For Example:

N: 5
ARR: 10 20 10 30 40
Here the maximum jumps that Ninja can take are [10, 20, 10, 30] as the difference between consecutive elements is [10, -10, 20]. 
So the maximum times Ninja needs to jumps is 4.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. Then test cases follow:

The first line contains an integer ‘N’ the size of the given array.

The second line contains ’N’ space-separated integers denoting the elements of the ‘ARR’.

Output Format :

For each test case, return an integer denoting the maximum number of jumps that Ninja can take.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
2 <= N <= 5000
1 <= ‘ARR[i]’ <= 10^9

Where ‘ARR[i]’ denotes the ith element of ‘ARR’.

Time Limit: 1 sec.

Sample Input 1 :

2
4
1 2 3 4 
6
2 3 2 2 1 3

Sample Output 1 :

1
4

Explanation of Sample Input 1 :

For the first test case, the maximum Jumps Ninja can take in one of the following paths is [1] or [2] or [3] or [4], so the maximum jumps are 1.
For the second test case, the maximum Jumps Ninja can take in one of the following paths is  [2, 3, 2, 3] or [2, 3, 1, 3], so the maximum jumps are 4.

Sample Input 2 :

Sample Output 2 :

1
4

Console