Let $A[1...N]$ be an Array of size $N$ with maximum element $\max$.I want to transform array $A$ such that after transformations all elements of $A$ contain $\max$, i.e. after transformation $A = [\max,\max,\max,\max,\dots,\max]$.In one step, I can apply the following operation to any consecutive sub-array $A[x..y]$:Assign to all $A[i]$ with $x \leq i \leq y$ the median of subarray $A[x..y]$.We consider as median always the $\left\lceil \frac{n+1}{2} \right\rceil$-th element in an increasingly sorted version of $A$.What is the minimum number of steps needed to transform $A$ as desired? If it helps, assume that $N\leq 30$.Example 1:Let $A = [1, 2, 3]$. We need to change it to $[3, 3, 3]$. The  minium number of steps is two, first for subarray $A[2..3]$ (after that $A$ equals to $[1, 3, 3]$), then operation to $A[1..3]$.Example 2:$A=[2,1,1,2]$.The  min step is  two. The median of subarray $A[1..4]$ is $2$ (3rd element in $[1,1,2,2]$. Apply the operation to $A[1..4]$ once and we get $[2,2,2,2]$.
array median transformation using the min number of steps
algorithms;arrays