"Crests And Troughs"
Given an array of n elements, find out all the crests and troughs along with their lengths. Find the absolute difference between indexes of longest and shortest crests as well as troughs and display the maximum of both.
• An element is said to be crest ,if both it's previous and next elements are less than the current element.
• An element is said to be trough , if both it's previous and next elements are greater than the current element.
Note: The first and last elements are neither crests nor troughs.
• In case of multiple occurrences of shortest crest/trough consider the left most one as shortest and right most one as longest.
• Print -1 if at least one crest and trough doesn't exist.
Input Format
---------------------
The first line contain an integer, t denoting the number of testcases.
The first line of each test case contains an integer, n denoting the size of the arr.
The second line of each test case contains n space-separated integers describing the elements of array.
Constraints
4<=n<=10e9.
0<=arr[i]<=n
Output Format
--------------------------
For every test case print the required output in a new line.
Sample Input 1
1
8
3 6 2 8 9 5 10 1
Output
2
Explanation
-------------------
The crest with maximum length (length --->10 - 1 =9) exists at index 6.
The crest with minimum length (length ---->9 - 8 =1) exists at index 4.
The trough with maximum length (length---> 8 - 2=6) exists at index 2.
The trough with minimum length (length ---> 6 - 2 = 4) exists at index 2 (troughs with length 4 exists at two indexes 2 and 5, but take trough at index as shortest trough as it is left most ).
Print 2 as (difference between indexes of longest and shortest crests ) 6 - 4 > 2 - 2 (differences between indexes of longest and shortest troughs).
can u send the code of this question bro
ReplyDeletesir can you send the code
ReplyDeleteCan you please send any hint for the solution for this problem??
ReplyDeletetest_case=int(input())
ReplyDeletefor test in range(test_case):
size=int(input())
line = input()
line = line.strip().split(" ")
minci=-1
maxci=-1
minti=-1
maxti=-1
max_c=-1
max_t=-1
min_c=9999999999
min_t=9999999999
numbers=list()
y=list()
x=list()
for number in line:
numbers.append(int(number))
y.append(int(number))
x.append(int(number))
x.sort()
if max(numbers) == min(numbers) or y == x:
print(-1)
continue
for i in range(1,size-1):
if numbers[i-1] > numbers[i] and numbers[i+1] > numbers[i]:
if numbers[i-1]-numbers[i]>=max_t or numbers[i+1]-numbers[i]>=max_t:
if numbers[i-1]-numbers[i]>numbers[i+1]-numbers[i]:
max_t = numbers[i-1]-numbers[i]
else :
max_t = numbers[i+1]-numbers[i]
maxti=i
if numbers[i-1]-numbers[i]=max_c or numbers[i]-numbers[i+1]>=max_c:
if numbers[i]-numbers[i-1]>numbers[i]-numbers[i+1] :
max_c = numbers[i]-numbers[i-1]
else:
max_c = numbers[i]-numbers[i+1]
maxci=i
if numbers[i]-numbers[i-1]maxci-minci:
print(maxti-minti)
else:
print(maxci-minci)
numbers.clear()