[Java] 백준 1912번 : 연속합

문제

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

 

접근 방법

1. 각 수가 주어졌을때 연속된 수를 선택(1~N개)해서 구할 수 있는 합중 가장 큰 합을 구하는 문제이다.
2. 따라서 이전부터 계속 연속한 값과, 현재부터 연속된 값의 경우를 비교하며 큰 값만 담아주면 된다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int N;
    private static int[] arr,prefix;
    private static int max = Integer.MIN_VALUE;


    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

        arr = new int[N+1];
        prefix = new int[N+1];

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

    //실행
    public static void process() {
        for(int i = 1 ; i <= N ; i++){
            prefix[i] = Math.max(prefix[i-1]+arr[i],arr[i]);

            max = Math.max(max,prefix[i]);
        }
        System.out.println(max);

    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}