[JAVA] 백준 1912번 - 연속합

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

1912번: 연속합

 

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        int[] dp = new int[n];


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

        dp[0] = arr[0];
        int max=dp[0];

        for(int i=1; i<n; i++){
            dp[i] = Math.max(arr[i], dp[i-1]+arr[i]);
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}

 

 

 

dp[i] = i번째 위치에서의 연속된 수들의 최댓값 

 

연속된 수들의 합을 따져야 한다.

(i번째 이전에 연속된 숫자들의 합 + i번째 값)과 (i번째 값) 을 비교 해, 더 큰 값을 dp[i] 에 저장한다.

 

 

다음 표는 위는 arr, 아래는 dp배열을 나타낸 것이다.

10	-4	3	1	5	6	-35	12	21	-1
10	6	9	10	15	21	-14	12	33	32

 

7번째까지는 계속 dp[i-1] + arr[i]로 dp[i]가 저장되다가, 8번째에 숫자 12를 만났을 때 처음부터 8번째까지 모든 숫자들의 합인 (-14+12)=(-2) 보다 12가 크기 때문에 12가 저장되는것을 볼 수 있다. 이 부분이 문제를 풀 수 있는 핵심이였다고 생각한다. 

 

이러한 dp배열에서의 최댓값을 찾아주면 된다.