백준 BOJ 2670 - 연속부분최대곱

간단한 DP. 그런데 N범위가 작아서

브루트포스해도 될거같다.

 

dp[k]를 k번째 수를 곱할때의 최대값 으로 정한다.

그러면 dp[k]를 만들 수 있는 방법은

기존까지의 수들을 싹 버리고 k번째 수만을 가지고 새로 시작하는 경우이거나,

기존까지의 수들 = dp[k-1] 에 k번째 수를 곱하는 경우 두가지로 나뉘게 된다.

이렇게 짜주면 쉽게 AC를 받을 수 있다.

 

#include <stdio.h>

double arr[12345] = {0.0};
double dp[12345] = {0.0};

double max(double a, double b){return a>b?a:b;}

int main(){
	int n;
	double ans = -1;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%lf", &arr[i]);
		dp[i] = arr[i];
	}
	for(int i=1; i<n; i++) dp[i] = max(arr[i], dp[i-1]*arr[i]);
	for(int i=0; i<n; i++) ans = max(ans, dp[i]);
	
	printf("%.3lf", ans);
	return 0;
}