[BOJ 2670] 연속부분최대곱 (Java, DP)

 

 

---

문제 링크 

https://www.acmicpc.net/problem/2670

2670번: 연속부분최대곱

---

문제 풀이 

- 시간복잡도 O(N) 

- DP 배열의 경우 이전 값과 곱한 경우와 자기 자신과 비교했을 때 더 큰 값을 갱신 

1	2	3	4	5
1.1	0.7	1.3	0.9	1.4
1.1	0.77	1.3	1.117	1.638

 

*참고. 자바 소수점 처리

https://bullie.tistory.com/7

[Java] 자바 소수점 원하는 자리수 만큼 출력

---

제출 코드

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

public class Main {
    
    static int N;

    static double[] DATA, DP;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        DATA = new double[N];
        for(int i = 0; i < N; i++) {
            DATA[i] = Double.parseDouble(br.readLine());
        }

        DP = new double[N];
    }

    static void pro() {
       DP[0] = DATA[0];
       for(int i = 1; i < N; i++) {
            DP[i] = Math.max(DATA[i], DP[i - 1] * DATA[i]);
       }

       System.out.printf("%.3f", Arrays.stream(DP).max().getAsDouble());
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}