Lexicographically Maximum Final Sequence
MediumAsked in:Amazon•Stage:Online Assessment
Problem Statement
Given an array A of n integers, you may repeatedly take either the leftmost or rightmost element of the current array and append it to a new sequence. After all elements are taken you obtain a final sequence of length n. Compute the lexicographically maximum possible final sequence.
Input Format
The first line contains an integer n (the size of the array). The second line contains n space‑separated integers A[1],A[2],…,A[n].
Output Format
Print the lexicographically maximum final sequence as n space‑separated integers on a single line.
Constraints
- 1 <= n <= 10^5
- -10^9 <= A[i] <= 10^9
- Expected time complexity O(n) or O(n log n)