Citadel OA | Global Maximum | Citadel Online Assessment Question
Consider an array of distinct positive integers where elements are sorted in ascending order. We want to find all the subsequences of array consisting of exactly m elements. For example, given array a=[1,2,3,4], the subsequences consisting m=3 elements are [1,2,3], [1,2,4], [1,3,4], and [2,3,4]. Once we have all of the m-element subsequences, we find the value of globalMaximum using the following pseudocode:
globalMaximum = 0 for each subsequence, s, consisting of m elements { currentMinimum = 10^18 for each (x,y) pair of elements in subsequence s { absoluteDifference = abs(x - y) if absoluteDifference < currentMinimum { currentMinimum = absoluteDifference } } if currentMinimum > globalMaximum { globalMaximum = currentMinimum } }
Relevant Citadel OA Problems:
Input & Output
Input
arr — a sorted array of distinct integers
m — an integer, the subsequences' length
Output
the global maximum calculated per the pseudocode
Example
Input
arr = [2,3,5,9] m = 3
Output
3
Explanation
First find all subsequences of length m.
[2,3,5] [2,3,9] [2,5,9] [3,5,9]
The final answer is globalMaximum=3 for subsequence [2,5,9].
Constraints
2<=n<=10^51<=a[i]<=10^9- The array consists of distinct positive integers sorted in ascending order.
2<=m<=n