문제: 최대 연속 부분합 찾기
언어: 자바
이 문제는 여러 방법으로 풀 수 있다. 아주 쉽게(무식하게) 풀고자 한다면 주어진 배열 {A1, A2, ..., An} 의 모든 서브배열을 구하고 이중 가장 큰 값을 찾는 것이다. 하지만 전체 탐색 시간은 n의 세제곱이 된다.
가능한 시간 내에 풀기 위해서는 Greedy 하게 풀거나 Dynamic 하게 풀 수 있다.
[Greedy 방법]
Wiki에 Maximum Subarray Problem 에서 kadane's algorithm 이 나와 있다. Kadane's algorithm 은
1) 현재의 조회하는 숫자를 해에 추가 하였을 때 0보다 작게 되면 현재까지의 해를 0으로 설정
2) 지금까지 최대 SubArray의 값보다 1)의 값이 크면 지금까지의 최대 SubArray값을 1)의 값으로 설정
하는 것이다.
Wikipedia의 Algorithm 정의는 다음과 같다.
Greedy한 부분은 바로 1)번이다. 즉 현재 상태에서 부분 문제의 최적해를 구한 뒤 이를 부분해 집합에 추가하는 부분이 된다. 자바 코드로 간단하게 구현 가능하다.
[Dynamic 방법]
동적 프로그래밍 방법은 점화식 방법으로 사고하는 것이다.
즉 MS(K) 가 Ak 까지의 최대 연속 부분합이라고 한다면 점화식은 다음과 같이 구성된다.
1) k가 0이면 MS(0)=MAX{A0, 0}
2) MS(k) = MAX{MS(k-1)+Ak , Ak };
답은 MS(0) 부터 MS(k) 까지 값들 중 최대의 값을 구하는 것이다. 다음은 자바로 구현한 코드이다.
