실력키우기 연속부분최대곱(C++)

2101 : 연속부분최대곱

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 740 회    시도횟수: 2489 회   

N개의 양의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면,

 

색칠된 부분의 곱이 최대가 되며, 그 값은 1.638이다.

결과는 double형의 범위를 넘지 않는다.

 

첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다.

계산된 최대값을 소수점 이하 넷째 자리에서 반올림하여 소수점 이하 셋째 자리까지 출력한다.

[Copy] 8 1.1 0.7 1.3 0.9 1.4 0.8 0.7 1.4

[Copy] 1.638

출처 : KOI 전국 1996 중1

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

/**************************************************************     Problem: 2101     User: a132034     Language: C++     Result: Success     Time:2 ms     Memory:1264 kb ****************************************************************/     #include    <cstdio> #pragma warning(disable :4996)   double a[11111]; double D[11111]; int main() {     int N;     scanf("%d", &N);     for (int i = 1; i <= N; ++i)         scanf("%lf", &a[i]);       double max = 0;     for (int i = 1; i <= N; ++i)     {         D[i] = (1 > D[i - 1] ? 1 : D[i - 1]) * a[i];;         if (D[i] > max)             max = D[i];     }     printf("%0.3lf ", max);       return 0; }

연속부분 최대합과 전혀 다르지 않게 풀었다. 

변한점이 있다면 이전까지의 최대합이 0보다 작은 경우 -> 이전까지의 최대곱이 1보다 작을 경우

그것 말고는 딱히 없다. 

다이나믹으로 풀었는데 식만 안다면 어렵지 않다. 

D[i]는 i번째를 포함하는 연속부분 최대곱이다. 

때문에 D[i-1]이 1보다 작다면 D[i]는 a[i] 그대로가 될 것이고 D[i-1]이 1보다 크다면 D[i]는 D[i-1]*a[i]가 될 것이다. (26번 라인)

모든 D[i] 중 가장 큰 값이 문제가 원하는 값이다.