Minimize Maximum Difference of Grouped Elements
Given an array of N integers, partition its elements into contiguous subarrays (groups). All elements within a single group must have values between X and Y, inclusive. Your goal is to minimize the maximum difference between any two elements within the same group, over all possible partitions. Find the smallest possible value for this maximum difference.
Input
The first line contains an integer N. The second line contains N space-separated integers A_1, A_2, ..., A_N.
Output
Print a single integer representing the minimum possible maximum difference.
Constraints
1 <= N <= 200000 1 <= A_i <= 10^9
Example 1
5 1 5 2 8 4
0
The array can be partitioned into [1, 5, 2] (max diff 4) and [8, 4] (max diff 4). The maximum difference is 4. Or partition into [1], [5, 2], [8, 4]. Max diff is 4. If we try to make groups smaller, like [1, 5], [2, 8], [4], max diffs are 4, 6, 0. Overall max diff 6. Minimum possible max diff is 4.
Example 2
7 10 20 30 40 50 60 70
0
The array can be partitioned into groups of size 1: [10], [20], ..., [70]. Each group has max diff 0. The minimum possible max difference is 0.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 5 2 8 4
7 10 20 30 40 50 60 70