백준 1912 - 연속합

Java

1912 번 - 연속합

문제

접근 방법

n이 최대 100,000 임으로 2중 반복문은 시간 초과를 유발한다.
따라서, 누적 합을 담을 dp 1차원 배열을 사용한다.

시작부터 각 수열의 값을 하나씩 더해보며 계속하여 값을 누적할지, 아니면 새롭게 시작할 것인지 정한다.

만약 “지금까지 누적된 값(dp) + 현재 갑” 보다 “현재 값”이 더 크면, dp의 값을 현재 값으로 갱신한다.
이말은 즉, 현재 값부터 새롭게 누적 합을 계산한다는 뜻이다.

예시로, [1, 2, -4, 5, 2] 라는 수열이 있다고 생각하자.
그렇다면 3번째 값 -4까지 더한 누적 값은 “1 + 2 - 4 = -1”이다.

여기서 5를 만났을 때, 누적 합(-1) + 현재 값(5) < 현재 값(5) 이므로, 현재 값으로 dp를 갱신하고 이 값부터 누적합의 시작한다.

따라서, 누적합 5에서 2를 더한 7이 최대 연속 합이 된다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, result = -1001;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	n = stoi(br.readLine());
    	int[] arr = new int[n];
    	int[] dp = new int[n];
    	
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		arr[i] = stoi(stk.nextToken());
    	}
    	dp[0] = arr[0];
    	result = arr[0];
    	
    	for(int i = 1; i < n; i++) {
			// 지금까지 더한 누적합 + 현재 값과 현재 값을 비교한다.
    		dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
    		result = Math.max(dp[i], result);	// 최대 연속 합
    	}
    	
    	
    	System.out.println(result);
    	
    	br.close();
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점