※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.
문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
풀이
수열이 주어지면 부분 수열 중 합이 가장 큰 것을 찾아 그 합을 출력해야한다. 부분수열의 길이는 1일수도 있고 더 길 수도 있다. 물론 당연히 원래 수열보다 크지는 않을 것이다.
이를 풀기위해서는 물론 모든 부분 수열의 합을 계산해 볼 수도 있겠지만 매우 비효율적이며 시간도 많이 걸린다. 주어지는 수열의 길이가 최대 10만개 까지이기 때문이다.
이 문제를 풀기 위해서는 카데인 알고리즘이라는 것을 알고 있어야한다. 이게 무엇인지 알아보자.
카데인 알고리즘
Kadane’s Algorithm
이 알고리즘은 조셉 본 카데인(Joseph Born Kadane)이 만든 알고리즘으로, 시간복잡도가 O(n)인 수열의 부분 수열 중 최대합을 구하는데 사용되는 알고리즘이다.
def max_subarray(numbers):
"""Find the largest sum of any contiguous subarray."""
best_sum = - infinity
current_sum = 0
for x in numbers:
current_sum = max(x, current_sum + x)
best_sum = max(best_sum, current_sum)
return best_sum파이썬 코드로 나타내면 위와 같다. 위 함수에 단순히 수열을 넘겨주면 최대 합이 계산되서 반환된다. 이제 어떤 식으로 돌아가는지 파악해보자.
일단 최종적으로 반환할 최대값을 저장할 변수를 선언하고 값을 가능한 가장 작은 값으로 지정한다. 자바 같으면 Inger.MIN_VALUE 같은 식으로.
현재 인덱스 까지의 최대합을 임시로 저장할 변수도 하나 만들어준다.
수열의 각 숫자를 처음부터 반복문으로 순환하면서 값을 갱신한다.
current_sum에는 현재 숫자와 이전 숫자 까지의 최대 부분합에 현재 숫자를 더한 값 중 더 큰값을 지정한다. 그리고 current_sum이 기존의 best_sum과 비교해서 더 크면 best_sum을 업데이트 해준다.
놀랍게도 이게 끝이다. 나도 처음에 보고는 정말 이걸로 되는가 싶었다. 정말로 끝이다.
코드
public static StringBuilder sb;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
String[] inputs = br.readLine().split(" ");
int[] nums = new int[N];
for(int i=0; i<N; i++){
nums[i] = Integer.parseInt(inputs[i]);
}
sb.append(solve(nums));
System.out.println(sb.toString());
br.close();
}
public static int solve(int[] nums){
int tmp_max = 0;
int max = Integer.MIN_VALUE;
for(int n : nums){
tmp_max = Math.max(n, tmp_max+n);
if(max < tmp_max) max = tmp_max;
}
return max;
}위 내용을 그대로 코드로 옮겨주면 된다.
댓글