연속합 (백준 1912)

 

여기서 포인트는, 언제 새로 연속을 끊어야 하는가? 이다.

음수 값이 나온다고 무조건 끊고 다시 생각해야하게 아니다.

 

예제 2번을 보면 -4 > 3 > 4 이다.

저 3개의 합은 +3으로, -4가 나오더라도.

 

연속 수에서 count를 끊고, 다시 새는 순간은 여태 누적합이 음수가 되는 순간이다.

 

그래서 난 이 문제를 풀 때,

 

누적합과 dp 배열을 각각 만들어서 dp[i]의 값은 sum[i]와 dp[i-1] 중 비교를 통해 선택했다.

(Data)10	-4	3	1	5	6	-35	12	21	-1
(Sum)10	6	9	10	15	21	-14	12	33	32
(DP)10	10	10	10	15	21	21	21	33	33

dp[i]의 값은 i까지 연속합중 최고의 값을 말한다.

저기 표 가운데를 보면, 음수일 때는 그 다음 sum값을 초기화 해주는게 포인트이다.

음수라면, 양수를 더하는 것보다, 그냥 다시 시작하는게 최대 합 측면에선 맞기 때문이다.

 

dp문제들은 표를 그리면서 이해하려고 해보면 쉽다.

특히 무작정 표를 따라 그리기 보다는

각 칸의 의미들을 생각해고 넣어야 한다.

 

 

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

public class Q1912 {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] data = new int[num];
		
		int[] dp = new int[num];
		int[] sum = new int[num];
		
		for(int i = 0; i<num; i++) {
			data[i] = Integer.parseInt(st.nextToken());
		}
		
		dp[0] = data[0];
		sum[0] = data[0];

		int max = Integer.MIN_VALUE;
		
		if(num == 1) {
			System.out.print(data[0]);
			return;
		}
		
		
		for(int i = 1; i<num; i++) {
			
			if(sum[i-1] > 0) {
				sum[i] = sum[i-1] + data[i];
			}else {
				sum[i] = data[i];
			}

			dp[i] = Math.max(sum[i], dp[i-1]);
			
			if(dp[i] > max) {
				max = dp[i];
			}
		}
		
		System.out.print(max);
	}
}

 

항상 input에 대해선 주의하는 것을 잊지 말자.

만약 input의 개수가 1이라면,

굳이 계산할 필요없이 바로 해당 값을 출력하면 된다.