maximum sum
-
[문제해결을 위한 창의적 알고리즘] Maximum Sum (고급, p144)알고리즘 2017. 2. 1. 20:08
이 문제는 수열이 주어졌을때, 연속된 부분 수열의 합이 최대가 되는 값을 찾아 내는 문제이다. O(n^2)을 원하는 문제가 아니므로 점화식을 찾아내어 동적 계획법 (Dynamic Programming)으로 풀어야 하는 문제이다. 해설에서 잘 설명하고 있지만, k번째 항목으로 끝나는 부분 수열을 만든다고 하면, k-1번째까지의 최대 합에 k번째 값을 더한 값과 k-1번째까지의 합은 버리고 k번째 항목을 비교하여 둘 중 더 큰 값을 취하면 k번째 항목으로 끝나는 부분 수열의 최대값을 구할 수 있다. import java.util.Scanner; public class MaxSumSol148 { public static final int INF = 987654321; public static int[] S =..