DP - 1912. 연속합

문제

www.acmicpc.net/problem/1912

1912번: 연속합

 

잠깐만

값을 더해가는 도중, 어느시점에 초기화를 진행할 지 생각해보세요

 

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int inputNum = Integer.parseInt(st.nextToken());
		
		int maxSum = Integer.MIN_VALUE; 
		int tempSum = 0;

		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= inputNum; i++) {
			int value = Integer.parseInt(st.nextToken());
			tempSum = Math.max(tempSum + value, value);
			maxSum = Math.max(maxSum, tempSum);
		}
		
		System.out.print(maxSum);
	}
}

 

설명

tempSum을 더해가며 계산하면 되는데, 더하기를 중단해야할 시점이 있습니다.

바로, tempSum + value < value인 시점이죠.

제가 만든 예제를 한번 볼까요?

-2를 입력하면 tempSum은 -2가 되죠.

-3을 입력하면 max(-2-3, -3)을 선택해야 합니다. 더한 값인 -5보다는 입력값 -3이 더 크기 때문에 더할 필요는 없겠죠?

-4을 입력하면 max(-3-4, -4)을 선택해야 합니다. 더한 값인 -7보다는 입력값 -4가 더 크기 때문에 더할 필요는 없겠죠?

1을 입력하면 max(-4+1, 1)을 선택해야 합니다. 더한 값인 -3보다는 입력값 1가 더 크기 때문에 더할 필요는 없겠죠?

결과적으로 max값은 1이 됩니다.

 

문제 예제를 보면 다음과 같습니다.

 

추천 문제

skillist.tistory.com/213

121. Best Time to Buy and Sell Stock