Max Element in Prefix
EasyPractice library · +10 XPstackprefix sumsarrays
Given a sequence of N integers, print a sequence of N integers where the i-th integer is the maximum value among the first i elements of the input sequence.
For example, if the input is [3, 1, 4, 1, 5, 9, 2, 6], the output should be [3, 3, 4, 4, 5, 9, 9, 9].
Input
The first line contains an integer N. The second line contains N space-separated integers.
Output
Print N space-separated integers, where the i-th integer is the maximum of the first i input integers.
Constraints
1 <= N <= 1000 -10^9 <= elements <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
8 3 1 4 1 5 9 2 6
Output
3 3 4 4 5 9 9 9
The maximum of the first i elements for each i.
Example 2
Input
5 -2 -5 -1 -8 -3
Output
-2 -2 -1 -1 -1
Handles negative numbers correctly.
Hints
# 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
8 3 1 4 1 5 9 2 6
Example 2 input
5 -2 -5 -1 -8 -3