백준 2670번 : 연속부분최대곱

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

1. 문제 요약

N 개의 양의 실수가 있을 때 한개 이상의 연속된 수들의 곱이 최대값을 출력하는 문제

2. 알고리즘

O(N^2) 으로 풀었다.

반복문을 선언해서 현재 원소에서 다음 원소까지 모든 곱을 구하여 가장 큰값을 반환 하도록 하였다.

DP 를 사용하면은 O(N) 으로 풀수 있다고 한다.

float, double 출력시 자리수 출력에 유의하자.

3. 코드

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main() {
    
    std::ios::sync_with_stdio(false); cin.tie(0);
 
    int n; cin >> n;
 
    vector<double > arr(n);
    for(int i=0; i<n; i++)
        cin >> arr[i];
 
    double sol = -1;
 
    for(int i=0; i<n; i++) {
        double cand = 1;
        for(int j=i; j<n; j++) {
            cand = cand * arr[j];
 
            if(cand > sol) {
                sol = cand;
            }
        }
    }
 
    // 항상 잊지 말것 자리수 출력
    cout.setf(ios::fixed);
    cout.precision(3);
    cout << sol << "\n";
    return 0;
}