[Java] 백준 21758번 꿀 따기

누적합, 그리디 문제입니다.

벌 두마리의 위치와 꿀통의 위치를 적절히 두어서 최대 꿀의양을 출력해야합니다.
벌이 위치한곳의 꿀은 얻을 수 없으며, 벌은 꿀통이 향한 방향으로만 이동합니다.

가능한 경우는 3가지라고 생각했습니다.
1. 벌 벌 꿀통
2. 꿀통 벌 벌
3. 벌 꿀통 벌

1번과 2번의 경우
꿀통과 한마리의 벌은 끝에 두는것이 반드시 유리합니다. (그리디)
가운데 벌만 모든위치에 배치해서 크게 나온 꿀의 양을 얻을 수 있습니다.

3번의 경우
벌을 양쪽 끝에 두는것이 반드시 유리합니다. (그리디)
가운데 꿀통의 위치만 옮겨가면서 결과값을 얻습니다.

1, 2, 3번의 경우들을 모두 해서 가장 큰 결과값을 출력해주었습니다.

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int[] arr = new int[n];
    int[] sum1 = new int[n];
    int[] sum2 = new int[n];
    int result = 0;

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; ++i) {
      arr[i] = Integer.parseInt(st.nextToken());
    }

    sum1[0] = arr[0];
    sum2[n - 1] = arr[n - 1];
    for (int i = 1; i < n; ++i) {
      sum1[i] = sum1[i - 1] + arr[i];
      sum2[n - 1 - i] = sum2[n - i] + arr[n - 1 - i];
    }

    for (int i = 1; i < n - 1; ++i) {
      result = Math.max(result, sum1[i] + sum2[i] - sum1[0] - sum2[n - 1]);
      result = Math.max(result, sum1[n - 1] + sum1[n - 1] - sum1[0] - arr[i] - sum1[i]);
      result = Math.max(result, sum2[0] + sum2[0] - sum2[n - 1] - arr[n - 1 - i] - sum2[n - 1 - i]);
    }

    bw.write(result + "\n");
    bw.close();
  }
}