백준 1912 연속 합 (JAVA 자바 풀이)

백준 1912 연속 합 (JAVA 자바 풀이)

 

---

 

 

📌 문제 

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

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

 

 

⚔ 입력

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

 

 

📣 출력

첫째 줄에 답을 출력한다.

 

 

 

 

---

 

 

 

💎 문제 분석

 

 

sum 배열로 dp[]를 이용하는 것이 핵심이다.

 

 

 

 

💡 코드 구현

 

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

public class Main {

	private static long sum;
	private static int testCases;
	private static long[] numbers;
	private static long[] dp;

	public static void main(String[] args) throws IOException {

		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

		testCases = Integer.parseInt(bufferedReader.readLine());

		numbers = new long[testCases];
		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		for (int i = 0; i < testCases; i++) {
			int number = Integer.parseInt(stringTokenizer.nextToken());
			numbers[i] = number;
		}

		dp = new long[testCases];
		dp[0] = numbers[0];
		sum = numbers[0];

		sequenceSum();
		System.out.println(sum);
	}

	private static void sequenceSum() {
		for (int i = 1; i < testCases; i++) {
			dp[i] = Math.max(dp[i - 1] + numbers[i], numbers[i]);
			sum = Math.max(dp[i], sum);
		}
	}
}