Given an array A of size N, We want to perform several iterations as described below.
Select any index i such that 1 <= i <= N, Mark A[i] = 0, move left by filling each element one greater than it’s right
Similarly move right, and fill each element which is one greater than it’s left.
For example consider an array of length 5, and we choose the index 3, the array would be
A = [2, 1, 0, 1, 2]
If we perform several iterations by choosing different indexes each time,
we have to output the maximum number, each element can get during all the iterations.
Consider that we repeat the procedure for the above array with Index 2
A = [1, 0, 1, 2, 3]
So after two iterations at indexes 2, and 3, maximum elements would be
MAX_A = [2, 1, 1, 2, 3]
To find MAX_A, at first, it looks like we need to repeat the procedure m times for m indexes,
which leads to O(m*n) complexity solution.
What will be the maximum number an element can get? N-1
How? Lets consider the same array as above, choose index 1, the array would be
A = [0, 1, 2, 3, 4]
Choose index 5, the array would be
A = [4, 3, 2, 1, 0]
So it is enough to perform the iteration with the left most and right most indexes,
the maximum element at each index i would be max( abs(i-left), abs(i-right))
So the time complexity will be O(n).
Here is the C++ code for the same.
Problem Source: The Army – Codechef