DP. 연속합

문제

그냥 순서대로 더하는 수 중에 가장 큰값을 찾는 문제이다.

해결 방향성

이번에도 점화식을 찾아본다. 처음에는 이중반복문으로 브루트포스? 방식으로 풀어봤다. 역시 시간초과. 다른 방법이 필요했다.

코드

package dp;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

import static java.lang.Math.*;

public class SerialSum {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        long[] num = new long[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            num[i] = Long.parseLong(st.nextToken());
        }

        long[] dp = new long[N + 1]; // 1 ~ N
        long max = -1000;
        dp[0] = 0;
        for (int i = 1; i <= N; i++) {
            dp[i] = max(dp[i - 1] + num[i], num[i]);
        }

        for (int i = 1; i <= N; i++) {
            max = max(dp[i], max);
        }

        bw.write(String.valueOf(max));

        bw.flush();
        br.close();
        bw.close();
    }
}

깨달은점

이 문제는 여태까지 합을 더하면서, 더했을때 더 작아지면, 그 수를 버리고 다시 max값을 구하는 형태이다. Math.Max() 함수를 잘써야한다.... 그렇게 해서 구해진 dp[] 배열에는 가장 큰 수가 담겨지게 된다. 그걸 max로 찾아 구하면된다.