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

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
43/228
post-thumbnail

# Appreciation

/*
 * Problem :: 2670 / 연속부분최대곱
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 최대부분연속합은 DP 를 이용해서
 *   dp[i] = A[i] 를 오른쪽 끝으로 하는 구간의 최대 합으로 정의하면
 *   for (int i=1; i<N; i++) {
 *       dp[i] = A[i] + ((dp[i-1] > 0) ? dp[i-1] : 0)
 *   }
 *   으로 구할 수 있다
 *   + dp[i] 를 구할 때 dp[i-1] 가 음수이면
 *     구간의 최대 합을 감소시키기 때문에
 *     이를 더하지 않는 것이 dp[i] 를 최대화하는 것이다
 *     # 마찬가지로 최대부분연속곱도 DP 를 이용해서
 *       dp[i] = A[i] 를 오른쪽 끝으로 하는 구간의 최대 곱으로 정의할 수 있다
 *       -> 여기서는 dp[i] 를 구할 때 dp[i-1] 가 1보다 작으면
 *          구간의 최대 곱을 감소시키기 때문에
 *          이를 곱하지 않는 것이 dp[i] 를 최대화하는 것이다
 *          => for (int i=1; i<N; i++) {
 *                 dp[i] = A[i] * ((dp[i-1] > 1) ? dp[i-1] : 1)
 *             }
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    double A[N];
    for (int i=0; i<N; i++)
        cin >> A[i];

    // Process
    double dp[N];
    dp[0] = A[0];
    double ans = dp[0];
    for (int i=1; i<N; i++) {
        dp[i] = A[i] * ((dp[i-1] > 1) ? dp[i-1] : 1);
        ans = max(ans, dp[i]);
    }

    // Control : Output
    cout << fixed;
    cout.precision(3);
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글