[백준 알고리즘 자바] 1912: 연속합

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

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. i 번째 배열의 값을 기준으로 해서 왼쪽, 오른쪽에 대한 길이를 담을 배열들을 이용해서 수열 위치에 대한 각 길이를 구한다.

2. 길이를 구한 두 배열을 더한 후에 -1을 해서 중복값을 빼준다.

3. 가장 큰 길이(값)을 출력한다.

---

풀이과정(BufferedReader)

1. 수열을 담을 배열과 각 길이를 담을 배열을 선언한다.

• seq() : 입력받은 수열의 값들을 저장한다.
• val() : 각 값들의 합을 저장한다.

2. seq() 배열에 입력받은 값을 담는다.

• BufferedReader 등에 대한 자세한 설명은 아래 링크를 참조하여 더 자세히 알아볼 수 있다.
• '기초이론/JAVA' 

'기초이론/JAVA' 카테고리의 글 목록

3. val[ 0 ] 과 max 에 seq[ 0 ] 값을 넣는다.

• 0번째는 무조건 자기 자신이 들어가야 하기 때문이다.
• 마찬가지로, 0번째 값이 최대값일 경우를 위해 max 초기값을 seq[ 0 ] 로 정의한다.

4. 1부터 size 까지 돌아가는 for문을 통해 val[ ] 배열에 값을 넣는다.

 

5. val[ i ] 번째에는 'val[ i -1] + seq[ i ]' 와 'seq[ i ]' 중 더 큰 값을 넣는다.

• Math.max(a, b) : a 와 b를 비교하여 더 큰 값을 변수에 저장한다.
• val[i -1] : i 번째 앞에 있는 수들이 더해진 값을 의미한다. seq[ i ] 번째 즉, i 번째 인덱스의 수열 값
• seq[ i ] : i 번째 인덱스의 수열 값을 의미한다.
• 즉, 그 i 번째 전까지 더한 값에 i번째 수열 값을 더한 결과와 i 번째 수열의 값을 비교해서 더 큰 값을 넣는다.
• 예제 1번으로 보자면 i 가 3 일 때 val[i -1] 는 '10' 이고 seq[ i ] 는 1이기에 max에는 '10'이 들어간다. 

6. val[ i ] 와 max 값을 비교해서 더 큰 값을 max 에 넣는다.

 

7. 0번째 값이 최대값일 경우를 대비해서 seq[ 0 ] 과 max 중 더 큰 값을 출력한다.

---

답안소스

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int size = Integer.parseInt(br.readLine());
		int max;
		int[] seq = new int[size];
		int[] val = new int[size];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<size; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}
		
		val[0] = seq[0];
		max = seq[0];
		
		for(int i=1; i<size; i++) {
			val[i] = Math.max(val[i -1] + seq[i], seq[i]);
			max = Math.max(val[i], max);
		}
		
		System.out.println(Math.max(seq[0], max));
	}
}