[白俊]2670/連続部分最大乗
# 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 */
Reference
この問題について([白俊]2670/連続部分最大乗), 我々は、より多くの情報をここで見つけました
https://velog.io/@gglifer/백준-2670-연속부분최대곱
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
/*
* 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)
* }
*/
//
// 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 */
Reference
この問題について([白俊]2670/連続部分最大乗), 我々は、より多くの情報をここで見つけました https://velog.io/@gglifer/백준-2670-연속부분최대곱テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol