Largest Element in Prefix
MediumPractice library · +20 XPqueuemonotonic dequesimulation
Given an array A of N integers, for each element A[i], find the largest element among A[0], A[1], ..., A[i]. Print these N maximums in order.
Input
The first line contains an integer N. The second line contains N space-separated integers A_1, A_2, ..., A_N.
Output
Print N space-separated integers, where the i-th integer is the maximum value among the first i elements of the input array.
Constraints
1 <= N <= 200000; -10^9 <= A_i <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB13 hidden tests
Example 1
Input
5 1 3 2 4 5
Output
1 3 3 4 5
The maximums of prefixes [1], [1,3], [1,3,2], [1,3,2,4], [1,3,2,4,5] are 1, 3, 3, 4, 5.
Example 2
Input
4 5 4 3 2
Output
5 5 5 5
The maximums of prefixes [5], [5,4], [5,4,3], [5,4,3,2] are 5, 5, 5, 5.
Hints
Similar problems
- Longest Prefix With Maximum FrequencyMedium
- Sliding Window MinimumMedium
- Balanced Parentheses SubsequenceMedium
- Find the First Negative NumberEasy
- Maximum Subarray Sum with Fixed LengthMedium
- Queue ReverserEasy
More topics: Sliding Window problems, Queue and Deque problems, Simulation problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 3 2 4 5
Example 2 input
4 5 4 3 2