[백준] 1912번 : 연속합(JAVA)

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

1912번: 연속합

풀이

연속된 수의 합이 가장 큰 값을 구하는 문제입니다.

※ 주의 ※

1개가 될수 있고 배열 전체가 될 수 도 있음.

 

1개가 될 수 도 있기 때문에 num으로 먼저 받아두고

answer을 가장 작은 값이 -1000과 num의 처음값중 큰 값으로 선언해주고, for문을 돌려 sum배열을 구하면서 max값을 채웁니다.

answer하고 sum배열 중 큰값을 계속해서 answer에 넣어주면 구간 합 중 가장 큰 값을 구할 수 있습니다.

 

소스코드

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[] num = new int[size];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < size; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] sum = new int[size + 1];
		sum[1] = num[0];
		
		int answer = Math.max(-1000, sum[1]);
		for(int i = 1; i <= size; i++) {
			sum[i] = Math.max(sum[i - 1] + num[i - 1], num[i - 1]);
			answer = Math.max(answer, sum[i]);
		}
		System.out.print(answer);
	}
}