알고리즘 문제
[C/C++ 백준 2670번] 연속부분최대곱 (Silver 4)
새파란 공대생
2020. 12. 27. 16:11
2670번: 연속부분최대곱
N개의 양의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면, 색칠된
www.acmicpc.net
DP라는 것만 알고 있으면 쉽게 풀 수 있는 문제이다. dp[i]를 i를 마지막으로 하는 색칠의 곱이라고 하면, dp[i]는 num[i]와 dp[i-1]의 곱, 그리고 num[i]중 최대값이 된다.
#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
int N;
double dp[10000], num[10000], maxi = -1;
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf("%lf", &num[i]);
if(i==0)
dp[i] = num[i];
else{
dp[i] = max(num[i], dp[i-1]*num[i]);
}
maxi = max(maxi, dp[i]);
}
printf("%.3lf", maxi);
}