[백준 문제 풀기] 1912번: 연속합 (DP, 자바)

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

 

문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력
첫째 줄에 답을 출력한다.

 

예제 입력, 출력

	예제 입력	예제 출력
1	10 10 -4 3 1 5 6 -35 12 21 -1	33
2	10 2 1 -4 3 4 -4 6 5 -5 1	14
3	5 -1 -2 -3 -4 -5	-1

 

사용 알고리즘

DP

 

코드 (자바)

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

// https://www.acmicpc.net/problem/1912
// 연속합
// Baekjoon1912

public class Main {
	
	static int max(int a , int b) {
		return a>b ? a : b;
	}
	
	public static void main(String[] args) throws Exception {
		
//		System.setIn(new FileInputStream("sample_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine().trim());
		
		int n = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine().trim());
		int[] inArr = new int[n+1];
		int[] dp = new int[n+1];			// 최대합을 저장할 dp 배열
		int maxSum = -Integer.MAX_VALUE;	// 가장 큰 구간합을 저장할 변수
		
		for (int i=1 ; i<=n ; i++) {
			inArr[i] = Integer.parseInt(st.nextToken());
			dp[i] = max (dp[i-1] + inArr[i] , inArr[i]);		// 직전까지의 최대합과 현재의 값을 더한것과 현재의 합을 비교해서 큰거 선택 (줄었다면 최대가 아니므로 새로 시작하는 개념)
			maxSum = max (maxSum, dp[i]);
			
		}
		
		System.out.println(maxSum);
	}

}

/* [인터돌™] 공부 해보자!! 열심히~~~ http://globalhost.tistory.com */