[백준OJ] 2670번 연속부분최대곱

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

2670번: 연속부분최대곱

---

 

풀이

dp를 이용하여 문제를 해결했다.

먼저 dp[i][0]= i번째 원소를 포함하지 않는 현재까지의 최대곱을 의미하고, dp[i][1]= i번째 원소를 포함한 상태에서의 최대곱을 의미한다.

 

i번째 원소를 포함하지 않는 현재까지의 최대곱은, i-1번째를 포함했을때와 포함하지 않았을때의 최대곱중 더 큰값을 택하면된다.

=>dp[i][0]=max(dp[i-1][0],dp[i-1][1]

 

i번째 원소를 포함하는 경우는 두가지 경우이다. i-1번째원소와 연결이 된 경우, i번째 원소가 스타트인 경우 두가지 이므로, 두가지경우중 더 큰값을 택하면된다.

=>dp[i][1]=max(dp[i-1][1]+array[i],array[i]);

 

n번째 원소까지 위를 실행한 뒤, dp[n-1][0]과 dp[n-1][1]중 더 큰 값을 택하면 된다.

 

시간복잡도

한번의 탐색으로 끝나기때문에 O(N)이 된다.

 

코드

import java.util.Scanner;

public class Main {
    static double[] array;
    static double[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        array=new double[n];
        dp=new double[n][2];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextDouble();
        }
        dp[0][0]=0;
        dp[0][1]=array[0];

        for(int i=1;i<n;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=Math.max(dp[i-1][1]*array[i],array[i]);
        }
        String ret=String.format("%.3f",Math.max(dp[n-1][0],dp[n-1][1]));
        System.out.println(ret);
        sc.close();
    }
}