algorithms 백준 (BOJ)

[BOJ]백준 1912번: 연속합 (baekjoon 1912)

2020.01.06 ·

(BOJ)백준 1912 - 1912번: 연속합

1912번: 연속합

[BOJ] 백준 (1912)

백준 1912 - 1912번: 연속합

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

코드

import java.io.*;
//DP[i] = (i번째 수를 구간의 마지막으로 하는 최대 연속구간합)
public class B1912 {
    static int N, max = Integer.MIN_VALUE;
    static int[] a = new int[100001];
    static int[] dp = new int[100001];
    static String[] ins;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        ins = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(ins[i]);
            max = Math.max(max, a[i]);
        }
        dp[0] = a[0];
        for (int i = 1; i < N; i++) {
            dp[i] = Math.max(dp[i - 1] + a[i], a[i]);
        }
        for (int i = 0; i < N; i++) {
            max = Math.max(dp[i], max);
        }
        bw.write(max + "\n");
        bw.flush();bw.close();
    }
}

설명