[백준][JAVA] 1912번: 연속합

 

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

1912번: 연속합

https://st-lab.tistory.com/140

[백준] 1912번 : 연속합 - JAVA [자바]

혼자 풀지 못해서 위의 분의 글을 참고했다.

 

그냥 여기서는 나의 차후 복습을 위해 내가 이해한 해석법?을 기록하려고 한다.

 

Integer[] d - 해당 값이 0은 물론 음수도 가능하기 때문에 0과 음수 값으로는 방문확인을 할 수 없다.

그래서 null이 들어갈 수 있는 Integer형으로 쓴다.

 

d[i] - 각 자리수의 연속해서 더했을때 만들 수 있는 최댓값이 들어온다.

d[i] = Math.max(re(i-1)+arr[i], arr[i]); - arr[i]앞쪽에서 연속한 값을 더한 값과 arr[i]만 봤을 때 무엇이 더 큰지 확인해준다. 

max - 우리가 구해야하 하는 수

- Integer[] d로 각 자리수에서 연속한 값을 더한 값중 제일 큰 값을 구했다. 이중 최댓값이 우리가 구해야 할 값이다.

import java.util.*;
import java.io.*;
class Main{
    static Integer[] d;
    static int[] arr;
    static int N;
    static int max;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)) ;
        N = Integer.parseInt(br.readLine());
        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        d = new Integer[N];
        d[0] = arr[0];
        max = arr[0];
        
        re(N-1);
        System.out.print(max);
    }
    public static int re(int i){
        if(d[i] == null){
            d[i] = Math.max(re(i-1)+arr[i], arr[i]);
            max = Math.max(max, d[i]);
        }
        return d[i];
    }
}