[BaekJoon] 15560 구간 합 최대? 1 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/15560

2.  문제

3.  소스코드

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

public class Main {
    static int seriesLength;
    static int queryCount;
    static int u;
    static int v;
    static int[] series;
    static int[] seriesPrefixSum;
    static int[] prefixSum;
    static int[][] queries;

    static void input() {
        Reader scanner = new Reader();

        seriesLength = scanner.nextInt();
        queryCount = scanner.nextInt();
        u = scanner.nextInt();
        v = scanner.nextInt();

        series = new int[seriesLength + 1];
        seriesPrefixSum = new int[seriesLength + 1];
        prefixSum = new int[seriesLength + 1];
        for (int idx = 1; idx <= seriesLength; idx++) {
            series[idx] = scanner.nextInt();
            seriesPrefixSum[idx] = seriesPrefixSum[idx - 1] + series[idx];
            prefixSum[idx] = u * seriesPrefixSum[idx] + v * idx;
        }

        queries = new int[queryCount][3];
        for (int queryIdx = 0; queryIdx < queryCount; queryIdx++) {
            queries[queryIdx][0] = scanner.nextInt();
            queries[queryIdx][1] = scanner.nextInt();
            queries[queryIdx][2] = scanner.nextInt();
        }
    }

    /*
     * 주어진 수열의 누적합을 더하고 해당 누적합을 기반으로 첫 번째 쿼리의 식을 적용한다
     *  - 이를 통해 수열의 첫 번째 원소부터 각 원소까지의 첫 번째 쿼리의 식을 적용한 값을 구할 수 있다
     * 첫 번째 쿼리라면 주어진 시작 인덱스부터 끝 인덱스까지 최댓값을 찾는다
     *  - 시작 인덱스부터 끝 인덱스까지 돌며 아래 작업을 진행한다
     *      - 시작 인덱스 바로 이전까지의 누적합부터 누적합의 최솟값을 갱신해나간다
     *      - 그리고 현재 인덱스까지의 누적합에서 최솟값을 빼며 각 인덱스까지의 최댓값을 구해나간다
     * 두 번째 쿼리라면 변경할 값과 원래 원소값 사이의 차이만큼 누적합에 더해준다
     */
    static void solution() {
        StringBuilder answer = new StringBuilder();
        for (int queryIdx = 0; queryIdx < queryCount; queryIdx++) {
            if (queries[queryIdx][0] == 0) {
                answer.append(findMaxSum(queries[queryIdx][1], queries[queryIdx][2])).append('\n');
                continue;
            }
            changeSeries(queries[queryIdx][1], queries[queryIdx][2]);
        }

        System.out.print(answer);
    }

    static int findMaxSum(int startIdx, int endIdx) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int idx = startIdx; idx <= endIdx; idx++) {
            min = Math.min(min, prefixSum[idx - 1]);
            max = Math.max(max, prefixSum[idx] - min);
        }
        return max - v;
    }

    static void changeSeries(int seriesIdx, int value) {
        int diff = value - series[seriesIdx];
        for (int idx = seriesIdx; idx <= seriesLength; idx++) {
            seriesPrefixSum[idx] += diff;
            prefixSum[idx] += u * diff;
        }
        series[seriesIdx] = value;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}