[JAVA] 백준 (실버2) 1912번 연속합

링크

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

---

문제 설명

정답률 37.155%
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

---

입력 예제

10
10 -4 3 1 5 6 -35 12 21 -1

---

출력 예제

33

---

풀이

DP 문제이다. 메모이제이션 배열에는 인덱스까지의 합을 저장하면 된다. 이때 부분합과 현재 값 중에 큰 값으로 저장을 한다. 가령 예제로 주어진 수열에서 -35까지의 부분합은 다음과 같다.

수열 부분합
 10   10
 -4    6
  3    9
  1   10
  5   15
  6   21
-35  -14
 12  (-2와 12 중 큰 값)
 21 
 -1

이때 그 다음 순서인 12까지의 부분합을 구한다면 이전 부분합인 -14에 12를 더해서 -2가 돼야 하지만 그냥 현재 값인 12로 저장하는게 최댓값이 되므로 12를 메모이제이션 배열에 저장한다. 그러면 다음 21은 12 + 21와 21 중 당연히 33이 더 크므로 부분합은 33이 된다.

전체 코드

//백준
public class Main {

    static Integer[] dp;
    static int[] array;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        dp = new Integer[N];
        array = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        dp[0] = array[0];
        recur(N - 1);
        int result = Arrays.stream(dp)
                .mapToInt(Integer::intValue)
                .max()
                .getAsInt();

        System.out.println(result);
    }

    //i번째 까지의 부분합
    static int recur(int i) {
        if (i == 0) {
            return array[i];
        }

        //탐색하지 않은 경우
        if (dp[i] == null) {
            //부분합과 현재값 중 큰값으로 저장
            dp[i] = Math.max(recur(i - 1) + array[i], array[i]);
        }

        return dp[i];
    }
}