All Tracks Algorithms Searching Binary Search Problem

Global Maximum
/

Binary Search, Greedy Algorithms

Problem
Editorial
Analytics

Consider an array of distinct positive integers where the elements are sorted in ascending order. We want to find all the subsequences of the array consisting of exactly \(m\) elements. For example, given array \(a=[1, 2, 3, 4]\), the subsequences consisting of \(m=3\) elements are \([1,2,3]\), \([1,2,4]\), \([1,3,4]\) and \([2,3,4]\). Once we have all 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 = 1e18
  for each (x,y) pair of elements in subsequence s {          // x != y
    absoluteDifference= abs(x-y)
    if absoluteDifference < currentMinimum {
         currentMinimum = absoluteDifference
    }
  }
  if currentMinimum > globalMaximum {
    globalMaximum = currentMinimum
  }
} 

 

Input:

  • First line contains a integer \(n\) , denoting number of elements.
  • Second line contains space seperated \(n\) integers ( \(a[0]\),\(a[1]\), ..... , \(a[n-1]\)) denoting the array elements.
  • Third line contains \(m\).

Output:

Output the value of globalMaximum.

Constraints:

  • \(1 \le n \le 2*{10^5}\)
  • \(1 \le a[i]\le {10^9}\)
  • \(1 \le m\le n\)

 

 

SAMPLE INPUT
4
2 3 5 9
3
SAMPLE OUTPUT
3
Explanation

\(a=[2,3,5,9]\)and \(m=3\).

All subsequences with \(m=3\) elements are:-

\([2,3,5]\) currentMinimum= \(1\)

\([2,3,9]\) currentMinimum= \(1\)

\([2,5,9]\) currentMinimum= \(3\)

\([3,5,9]\) currentMinimum= \(2\)

globalMaximum = \(max(1,1,3,2)=3\)

Time Limit: 1.5 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

Initializing Code Editor...
Notifications
View All Notifications

?