[백준 2670번] [동적 계획법] 연속부분최대곱

Approach

잘 생각해보면, 연속된 수들의 곱을 결정짓기 위해서는 이전 결과값이 사용된다는 느낌을 받을 수 있다. 

이 지점에서 DP를 활용할 수 있곘다는 느낌을 받으면 쉽게 풀 수 있다.

Let dp[i] : i번째 숫자로 끝나면서 연속된 수들의 곱이 최대가 되는 값

dp[i] = max(dp[i - 1] * v[i], v[i]) (단, v[i]는 i번째 수)

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int main(void){
    fastio;
    double dp[10001];

    int n;
    cin >> n;

    double f;
    cin >> f;
    dp[0] = f;

    for(int i = 1; i < n; i++){
        double a;
        cin >> a;
        dp[i] = max(dp[i - 1] * a, a);
    }

    double result = -1;

    for(int i = 0; i < n; i++){
        result = max(result, dp[i]);
    }

    cout << fixed;
    cout.precision(3);
    cout << result << "\n";

    return 0;
}