[백준 1912번] 연속합

문제 링크: 1912번 연속합

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

 

partialSum이 직전까지의 부분합보다 큰 경우에는 dp[i]는 partialSum이 될 것이고, 그렇지 않으면 dp[i]는 dp[i-1]과 같아야 한다. 하지만 partialSum이 음수인 경우에는 지금까지의 부분합을 버리고 0으로 초기화하는 과정이 선행되어야 한다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        /* input */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] t = br.readLine().split(" ");
        int[] arr = new int[n + 1];
        for (int idx = 1; idx <= n; idx++)
            arr[idx] = Integer.parseInt(t[idx - 1]);
        int[] dp = new int[n + 1];

        /* create dp */
        int partialSum = arr[1];
        dp[1] = arr[1];

        for (int i = 2; i <= n; i++) {
            if (partialSum < 0) partialSum = 0;
            partialSum += arr[i];
            if (partialSum > dp[i-1])
                dp[i] = partialSum;
            else
                dp[i] = dp[i-1];
        }

        System.out.println(dp[n]);
    }
}