The implementation from Geeksforgeeks https://www.geeksforgeeks.org/find-indices-of-all-local-maxima-and-local-minima-in-an-array/ is wrong. If you have consecutive-duplicates, things will gall apart!
Example 1: values = [ 1, 2, 3, 7, 11, 15, 13, 12, 11, 6, 5, 7, 11, 8]
The default implementation correctly identify "15" as a peak.
Example 2: values = [ 1, 2, 3, 7, 11, 15, 15, 13, 12, 11, 6, 5, 7, 11, 8]
The default implementation will mark "11" as local maxima because there are two consecutive 15's.
Below is code from geekforgeeks, with problem highlighted - when making greater/lesser comparison with left and right , if your neighbour's values == , then look further left or right:
def findLocalMaximaMinima(n, arr):
# Empty lists to store points of
# local maxima and minima
mx = []
mn = []
# Checking whether the first point is
# local maxima or minima or neither
if(arr[0] > arr[1]):
mx.append(0)
elif(arr[0] < arr[1]):
mn.append(0)
# Iterating over all points to check
# local maxima and local minima
for i in range(1, n-1):
# Condition for local minima
if(arr[i-1] > arr[i] < arr[i 1]): <-- Problem is here
mn.append(i)
# Condition for local maxima
elif(arr[i-1] < arr[i] > arr[i 1]): <-- Problem is here
mx.append(i)
# Checking whether the last point is
# local maxima or minima or neither
if(arr[-1] > arr[-2]):
mx.append(n-1)
elif(arr[-1] < arr[-2]):
mn.append(n-1)
# Print all the local maxima and
# local minima indexes stored
if(len(mx) > 0):
print("Points of Local maxima"\
" are : ", end ='')
print(*mx)
else:
print("There are no points of"\
" Local maxima.")
if(len(mn) > 0):
print("Points of Local minima"\
" are : ", end ='')
print(*mn)
else:
print("There are no points"\
" of Local minima.")
CodePudding user response：
Here's the fix (For some reason I can't upload the code there, so upload here instead):
from datetime import datetime
from typing import List
def is_greater(index1, index2, values, increment_when_eq : bool):
if values[index1]>values[index2]:
return True
elif values[index1]<values[index2]:
return False
else:
# Case when: values[index1] == values[index2]
index2_shifted = index2 1 if increment_when_eq else index2-1
if index2_shifted < len(values):
return is_greater(index1=index1, index2 = index2_shifted, values = values, increment_when_eq = increment_when_eq)
else:
return False
def find_local_max_min(values : List):
mx = []
mn = []
n = len(values)
if n==0:
return None
if(values[0] > values[1]):
mx.append(0)
elif(values[0] < values[1]):
mn.append(0)
for i in range(1, n-1):
if (not is_greater(i, i-1, values, False) and not is_greater(i, i 1, values, True)):
mn.append(i)
elif(is_greater(i, i-1, values, False) and is_greater(i, i 1, values, True)):
mx.append(i)
if(values[-1] > values[-2]):
mx.append(n-1)
elif(values[-1] < values[-2]):
mn.append(n-1)
return {
'local_max' : mx,
'local_min' : mn
}
if __name__ == '__main__':
values = [ 1, 2, 3, 7, 11, 15, 15, 13, 12, 11, 6, 5, 7, 11 , 8, 19, 19, 18, 18, 18, 15, 7, 3]
start = datetime.now()
local_min_max = find_local_max_min(values)
local_max = local_min_max['local_max']
local_min = local_min_max['local_min']
CodePudding user response：
I agree to Pranav that simply fix equality when making comparison will rectify the problem. The fix will be much more concise. Thanks Pranav
def findLocalMaximaMinima(n, arr):
mx = []
mn = []
if(arr[0] > arr[1]):
mx.append(0)
elif(arr[0] < arr[1]):
mn.append(0)
for i in range(1, n-1):
if(arr[i-1] >= arr[i] < arr[i 1]):
mn.append(i)
elif(arr[i-1] < arr[i] >= arr[i 1]):
mx.append(i)
if(arr[-1] > arr[-2]):
mx.append(n-1)
elif(arr[-1] < arr[-2]):
mn.append(n-1)
return mx, mn
arrs = [[ 1, 2, 3, 7, 11, 15, 15, 13, 12, 11, 6, 5, 7, 11, 8],
[4, 5, 6, 6, 6, 4, 3, 2, 1, 3, 5, 7, 9]]
for arr in arrs:
mx, mn = findLocalMaximaMinima(len(arr), arr)
print(*[f"{a}, {'max'*(i in mx)}, {'min' * (i in mn)}" for i, a in enumerate(arr)], sep='\n', end='\n\n')