Informatica Online Judge

  연속 부분 수열의 최대, 최소 [1380 / 0564]

Time Limit(Test case) : 3000 (ms)
Number of users who solved : 25   Total Tried : 106


The Champion of this Problem (C++) : gs15120 - 60ms / 1779byte
My Best Submission (C++) : N/A

[POJ]

Background

임의의 수열(범위 : -100<=k<=100, 수열 길이 : 1<=N<=1,000,000) 에서 연속 부분 수열 길이(1<=W<=N)을 왼쪽에서 오른쪽으로 한칸씩 이동하면서 최소값과 최대값을 찾는 프로그램을 작성하시오.

만약 주어진 수열의 크기가 5, 연속 부분 수열의 길이가 2이며, 각 원소가 다음과 같을 때,

4 5 -1 -3 -1

각 단계별로 최댓값과 최솟값은 다음과 같다.

단계 1: [4 5] -1 -3 -1 : 최댓값 5, 최솟값 4
단계 2: 4 [5 -1] -3 -1 : 최댓값 5, 최솟값 -1
단계 3: 4 5 [-1 -3] -1 : 최댓값 -1, 최솟값 -3
단계 4: 4 5 -1 [-3 -1] : 최댓값 -1, 최솟값 -3

이와 같은 값을 구한는 프로그램을 작성하시오.

Input

첫 번째 줄에 수열 길이(N)와 연속 부분 수열 길이(W)가 입력된다.

두 번째 줄에는 각 원소 k가 입력된다.

[입력값의 정의역]
1 <= N <= 1,000,000
1 <= W <= N
-100 <= k <= 100

Output

연속 부분 수열이 왼쪽에서 오른쪽으로 한 칸씩 이동할때마다 보이는 최소값과 최대값을 첫째줄, 둘째줄에 출력한다.

IO Example

입력
5 2
4 5 –1 –3 –1

출력
4 –1 –3 –3
5 5 –1 -1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]