[백준] 자바 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, -1, 5가 있다고 할때

경우의 수는 

1

-1

5

1,-1

-1,5

1,-1,5

가 있으므로 최대합은 5or 1,-1,5 즉 5입니다. 이것을 찾는 문제입니다.

 

배열을 2개 만들어서 하나에는 입력받은 값을, 하나에는 dp역할을 하는 최댓값을 넣을 것입니다.

최대값을 넣을 때는

이전 단계의 dp+현재 값 vs 현재 값을 비교해서 넣어주면 됩니다.

참고로 첫 번째 dp는 입력받은 첫 번째 값과 동일합니다.

위의 예제로 봤을 때,

입력받은 배열값	1	-1	5
dp	1	1+-1 vs -1 =>0	0+5 vs 5 =>5

 

따라서 나온 dp값들 중 최댓값을 출력하면됩니당

---

코드

import java.awt.desktop.SystemEventListener;
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

	/*
 	 1912 problem
	*/
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int num = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		ArrayList<Integer> arr = new ArrayList<>();
		ArrayList<Integer> result = new ArrayList<>();
		//수의 범위가 -1000부터이므로
		int max = -1000;
		
		for(int i=0; i<num; i++) {
			arr.add(Integer.parseInt(st.nextToken()));
		}
		result.add(arr.get(0));
		for(int i=1; i<num; i++) {
			
			result.add(i, Math.max(result.get(i-1)+arr.get(i), arr.get(i)));
			
		}
		
		for(int i=0; i<num; i++) {
			max = Math.max(max, result.get(i));
		}
		bw.write(String.valueOf(max));
		
		bw.flush();
		bw.close();
	}
	
}

---

주의

x