[백준] 25214번 - 크림 파스타 (Silver 4)

문제 링크

[백준] 25214번 - 크림 파스타 (Silver 4)

문제 설명

길이 N인 수열 A가 주어져 있다.
$k = 0, \cdots, N - 1$에 대해 $\textrm{max} \lbrace (A_j - A_i) \vert 1 \leq i \leq j \leq k \rbrace$ 값을 순서대로 출력한다.

정답 코드 및 설명

$A_j - A_i$값이 k에서 k+1로 넘어갈 때 바뀔 수 있는 경우가 무엇인지 생각해보자.
$A_{k+1} - A_i \left(0 \leq i \leq k\right)$ 중 가장 큰 값은 $A_i$가 가장 작을 때이고, 이 값이 기존의 값보다 크면 바꿔주면 된다.
$A_i$의 최소값을 계속해서 사용하게 되므로, 정답과 별개로 이를 따로 저장한다.
아래 코드에서는 최소값의 인덱스를 저장하였으나, 값으로 저장해도 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ25214 {
    int n, ans, minIndex, currI, currJ;
    int[] arr;

    void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[n];
        StringBuilder sb = new StringBuilder();
        ans = minIndex = currI = currJ = 0;
        for (int j = 0; j < n; j++) {
            arr[j] = Integer.parseInt(st.nextToken());
            if (arr[j] < arr[minIndex]) minIndex = j;
            if (arr[j] - arr[minIndex] > ans) {
                currJ = j;
                currI = minIndex;
                ans = arr[currJ] - arr[currI];
            }
            sb.append(ans).append(' ');
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws IOException {
        new BOJ25214().solution();
    }
}