글 읽기 - 1912 부분합 질문입니다. (문장이 애매해요..)

ljy8947 8년 전 0

연속된 숫자의 합이라고 하면 최소 2개 이상의 연속된 수의 합을 구해야 하는건가요?

그런데 n=1도 가능한 걸로 봐서는 그냥 하나의 숫자가 가장 클 경우 그게 답이 되는거 같기도 하네요..

(사실 둘 다 해봐도 답이 틀렸습니다가 나옵니다. 테스트 케이스를 여러가지 넣어보면 다 잘 나오는데도 그러네요.

아래는 2개 이상의 연속된 수의 합을 구하는 소스코드 입니다.)

시험해본 테스트 케이스

10
10 -4 3 1 5 6 -35 12 21 -1

6
6 -7 3 -1 5 2

5
-3 -4 -7 -1 -8

6
-1 -2 -7 5 3 7

5
-1 -7 -8 -4 99

4
1 2 -2 4

#include <stdio.h>

int n, A[101], sum[101], max=-987654321, tmp=1//0?;

int main()
{
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d", &A[i]);

    sum[0]= A[0];
    for(int i=1; i<n; i++)
            sum[i]= sum[i-1]+ A[i];

    for(int j=0; j<n-1; j++)
    {
        for(int i=tmp; i<n; i++)
        {
            if(max<sum[i])
                max=sum[i];
        }


        for(int i=j; i<n; i++)
            sum[i] -= A[j];
        tmp++;
    }
    //if(sum[n-1]>max)
    //    max=sum[n-1];

        printf("%d", max);

    return 0;
}

hahaha 8년 전 1

길이가 1일 때도 가능합니다.

위 소스에서 길이가 1일 때로 고치면 일단 n=1일때 max 답이 안 나옵니다.

그리고 n이 최대 10만인데, 배열 크기도 잘못 잡으셨습니다.

또한 O(n*n)이어서 시간초과가 나올 것 같습니다.

ljy8947 8년 전 0

@hahaha 해결했습니다. 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1912 부분합 질문입니다. (문장이 애매해요..)

ljy8947 8년 전 0

hahaha 8년 전 1

ljy8947 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말