[C] 백준 | 2670번 코드 - 연속부분최대곱

>문제

www.acmicpc.net/problem/2670 

2670번: 연속부분최대곱

> 핵심

DP

혹은

이중반복문

>풀이과정

이중 반복문을 돌려서도 시간초과 없이 풀어진다

다만 DP로 푸는것이 시간복잡도 면에서 훨씬 효율적인 알고리즘이라 할 수 있겠다

>깨달은점

DP는 아직 어렵다

근데 풀다보니까 뭔가 느낌은 오는 것 같다.

아직 더 많이 풀어봐야할듯

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

double dp[10002];

int main()
{
    int i, n;
    double max;

    scanf("%d", &n);
    scanf("%lf", &dp[0]);
    max = dp[0];
    for (i = 1; i < n; i++)
    {
        scanf("%lf", &dp[i]);

        dp[i] < dp[i] * dp[i - 1] ? (dp[i] *= dp[i - 1]) : dp[i];
        if (max < dp[i])
            max = dp[i];
    }

    printf("%.3lf", max);
    return 0;
}

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

double list[10002];

int main()
{
    int i, j, n;
    double max, tmp;

    scanf("%d", &n);

    for (i = 0; i < n; i++)
    {
        scanf("%lf", &list[i]);
    }

    max = 0;
    for (i = 0; i < n; i++)
    {
        tmp = list[i];
        if (max < tmp)
            max = tmp;
        for (j = i + 1; j < n; j++)
        {
            if (list[j] == 0.0)
                break;
            tmp = tmp * list[j];
            if (max < tmp)
                max = tmp;
        }
    }

    printf("%.3lf", max);
    return 0;
}