[백준] 연속합 (1912번)

문제 흐름

1. 문제 목표
   • 주어진 배열에서 연속된 부분 수열의 최대 합을 구하는 문제입니다.
   • 이 문제는 동적 프로그래밍을 이용하여 해결할 수 있습니다.
2. 입력 설명
   • 첫 줄에 정수 N (배열의 크기)를 입력받습니다.
   • 다음 줄에 N개의 정수 (각 원소의 값)를 입력받습니다.
3. 출력 설명
   • 연속된 부분 수열의 최대 합을 출력합니다.

 

핵심 아이디어

• 동적 프로그래밍(DP):
  • 현재 원소까지의 최대 합을 계산하면서 최댓값을 갱신합니다.
  • 배열의 각 원소를 순회하면서, 이전 원소와 현재 원소를 합치는 것이 더 큰 경우에 업데이트합니다.
  • 위 알고리즘을 카데인 알고리즘이라고 합니다.
• 점화식:
  • dp[i]는 dp[i-1] + arr[i] (현재 원소를 포함한 최대 합)과 arr[i] (현재 원소만) 중 큰 값을 선택합니다.

 

알고리즘 흐름

1. 입력 처리
   • 배열의 크기 N과 각 원소를 입력받습니다.
2. 최대 합 계산
   • 첫 번째 원소를 초기 최대 값으로 설정합니다.
   • 반복문을 통해 각 원소에 대해 현재까지의 최대 합을 계산하고, 이 최대 값을 갱신합니다.
3. 결과 출력
   • 최종적으로 구한 최대 합을 출력합니다.

---

정답은 더보기 클릭

import java.util.*;
import java.io.*;

public class Main {
	
	static int N;  // 배열의 크기
	
    public static void main(String[] args) throws IOException {
        
        Scanner in = new Scanner(System.in);
        
        N = in.nextInt();  // 배열 크기 입력
        
        int[] arr = new int[N];  // 배열 초기화
        
        // 배열 원소 입력
        for (int i = 0; i < N; i++) {
        	arr[i] = in.nextInt();
        }
        
        // 최대 합을 저장할 변수 초기화
        int max = arr[0];
        
        // DP를 통한 최대 합 계산
        for (int i = 1; i < N; i++) {
        	// 현재 원소와 이전 원소의 최대 합 또는 현재 원소만을 비교하여 업데이트
        	arr[i] = Math.max(arr[i-1] + arr[i], arr[i]);
        	// 최대값 갱신
        	max = Math.max(max, arr[i]);
        }
        
        // 결과 출력
        System.out.println(max);
    }
}