수학 알고리즘 예제(2). 백준 [1912] 연속합

백준[1912] - 연속합

연속되는 수 중 가장 큰 합을 찾아내는 문제이다.
DP로 간단하게 해결 가능하다

배열에 수들을 저장해 해당하는 index의 수가 선택되었을 경우,
이전까지의 합과 index의 요소 중 큰 수를 골라 저장하며 풀어 나간 뒤 가장 큰 수를 찾아 출력하면 된다.

 

다음은 Java로 작성한 코드이다.

import java.util.Scanner;

public class continuitySum {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int num = scan.nextInt();
		
		//수 배열
		int[] arr = new int[num];
		
		//큰 수 저장 배열
		int[] solution = new int[num];
		
		//입력
		for (int i = 0; i < num; i++) {
			arr[i] = scan.nextInt();
		}
		
		//기저 조건
		solution[0] = arr[0];
		
		//해당 index까지의 가장 큰 수 저장
		for (int i = 1; i < num; i++) {
			solution[i] = Math.max(arr[i], solution[i-1]+arr[i]);
		}
		
		//가장 큰 수 고르기 
		int max = solution[0];
		for (int i = 1; i < num; i++) {
			max = Math.max(max, solution[i]);
		}
		
		System.out.print(max);
	}

}