백준 2670번: 연속부분최대곱 (C++)

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

2670번: 연속부분최대곱

---

Solved By: DP

 

풀면서 Brute-Force 한 느낌이 들었습니다. 모든 시작점부터 n까지 다 곱해가면서 시작점마다 최댓값을 구하고, 또한 그 최댓값 N개 중에서도 최댓값을 구해야 합니다.

#include <iostream>
#define MAX 10001
using namespace std;

double arr[MAX];
double cache[MAX];
int n;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    
    double result = 0;
    
    // O(N^2) = O(100,000,000)
    for(int i = 1; i <= n; i++){
        double tmp = 1;
        double maxValue = 0;
        for(int j = i; j <= n; j++){
            tmp *= arr[j];
            maxValue = max(maxValue, tmp);
        }
        cache[i] = maxValue;
        result = max(result, maxValue);
    }
    
    cout.precision(3);
    cout << fixed;
    
    cout << result << '\n';
    return 0;
}