[백준/JAVA] 1912: 연속합

[백준/JAVA] 1912: 연속합

n개의 임의의 수열이 주어질 때 1개 이상의 수를 연속적으로 선택하여 최대 합이 되는 경우를 구하는 문제이다.

문제에서 최대합을 찾을 때 최대합의 일부분은 그 부분에 대한 최대합이라는 점에 유의한다.

위 예시에서 연속되는 부분 배열의 최대합은 $[4,-1,2,1]=>6$ 이다.

이때 배열에서 2의 뒷부분, 즉 $1,-5,-2,5$ 를 제외하고 그 앞부분만 본다면 $[-2,1,-3,4,-1,2]$ 의 배열이다. 이 부분배열에서의 최대합은 $[4,-1,2]=>5$ 이다.

마찬가지로 2 또한 제외한 -1의 뒷부분, $[-2,1,-3,4,-1]$ 만 본다면 이 부분배열에서의 최대합은 $[4, -1]=>3$ 이다.

즉 배열에서 구한 최대합 부분배열의 일부분또한 그 인덱스까지의 최대합이라는 점을 이해해야 한다. 이후 값의 최대합을 구하기 위해 이전 값의 최대합을 이용하기 때문에 DP로 접근이 가능한 문제이다.

동적 프로그래밍으로 연속되는 부분배열의 최대합을 구할때,

1. 현재까지의 부분배열의 합이 이전까지의 합보다 작아질 경우 값을 교체하지 않는다.
2. 각 위치에서 최대 부분 배열 합을 유지하면서 배열을 순회하면서, 현재 위치까지의 부분 배열 합을 계산한다. 이렇게 계산하면서 최대값을 갱신해 나간다.

만약 음수가 나왔다가 더 큰 양수가 나와 이전값보다 값이 커지는 경우 그 값을 교체하게 된다.

이렇게 동적 프로그래밍을 통해 배열의 최대합을 구하는 알고리즘을 Kadane's Algorithm이라고 한다.

소스코드

---

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

public class Main {
	public static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = 
        		new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        long arr[] = new long[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<n; i++)
        	arr[i] = Integer.parseInt(st.nextToken());
        
        // 수열 중 연속된 1개 이상의 수를 선택하여 최대 합을 구한다.
        System.out.println(maxSum(arr));
    }

    // SubArray의 최대값을 구하는 카데인 알고리즘
    public static long maxSum(long arr[]) {
    	long maxEnd = arr[0]; // 현재 위치에서의 최대합
    	long result = arr[0]; // 현재까지의 최대합
    	
    	for(int i=1; i<n; i++) {
    		maxEnd = Math.max(arr[i], maxEnd+arr[i]); // 현재 위치의 최대합을 구한다.
    		result = Math.max(result, maxEnd); // maxEnd와 result 중 더 큰 것을 최종값으로 한다.
    	}
    	return result;
    }
}