문제
양의 실수로 이루어진 수열에서 연속된 부분 수열의 곱이 최대가 되는 값을 구하라.
입력
첫째 줄에 N (1 이상 10,000 이하), 이후 N개의 양의 실수가 한 줄에 하나씩 주어진다.
출력
최대 연속 곱을 소수점 셋째 자리까지 출력한다.
예제
| 입력 | 출력 |
|---|---|
8 1.1 0.7 1.3 0.9 1.4 0.8 0.7 1.4 | 1.638 |
풀이
DP로 각 위치까지의 최대 연속 곱을 갱신한다.
arr[i]를 i번째까지 끝나는 최대 연속 곱으로 재사용한다arr[i] = max(arr[i], arr[i-1] * arr[i])로 이전까지의 곱을 이어갈지 새로 시작할지 결정한다- 모든 위치에서의 최대값이 답이다
핵심 아이디어: 최대 연속 부분합(카데인 알고리즘)의 곱 버전. 양의 실수이므로 음수 처리 없이 단순히 이전 곱을 이어가거나 새로 시작하는 두 경우만 비교하면 된다.
코드
package day399;
import java.io.*;
public class Day384BOJ2670연속부분최대곱 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
double arr[] = new double[n];
for (int i = 0; i < n; i++)
arr[i] = Double.parseDouble(br.readLine());
double max = 0;
for (int i = 1; i < n; i++) {
arr[i] = Math.max(arr[i], arr[i - 1] * arr[i]);
max = Math.max(max, arr[i]);
}
System.out.printf("%.3f", max);
}
}복잡도
- 시간: O(N)
- 공간: O(N)