MAXSUM 질문이요

  • dmatrix
    dmatrix

    MAXSUM

    위의 문제가 연속적으로 입력받은 숫자에서 최대 연속적인 부분합을
    찾는 문제인데 제가 작성한 답안에서 오류가 뭔지 모르겠습니다.

    알고리즘은 다음과 같습니다.

    1. 음수 또는 0 사이의 양수값을 모두 더합니다.
    2. 기존의 부분합보다 이 값이 크면 최대값을 변경합니다.

    문제에서 1 <= i <= j <= N 이므로 한자리의 합이 크면
    이 값이 최대부분합이 되는거라 한자리만 계산될지라도
    부분합을 최대로 하였습니다.

    #include <iostream>
using namespace std;

int GetMaxSum(int* const array, int size)
{
    int maxSum = 0;
    int index = 0;

    while (index != size)
    {
        int sum = 0;

        for (int i = index; i != size; index = ++i)
        {
            if (array[i] <= 0)
            {
                ++index;
                break;
            }
            else
            {
                sum += array[i];
            }
        }

        if (maxSum < sum)
        {
            maxSum = sum;
        }

        sum = 0;
    }

    return maxSum;
}

int main(int argc, char* argv[])
{
    int numOfCase = 0;
    cin >> numOfCase;

    for (int i = 0; i != numOfCase; ++i)
    {
        int size = 0;
        cin >> size;

        int* array = new int[size];
        for (int j = 0; j != size; ++j)
        {
            cin >> array[j];
        }

        cout << GetMaxSum(array, size) << endl;

        delete array;
    }

    return 0;
}

    9년 전
4개의 댓글이 있습니다.
  • Signin
    Signin

    최대 합이 꼭 양수만으로 이루어지지는 않을 것 같습니다.


    9년 전 link
  • dmatrix
    dmatrix

    최대합이 양수가 아니면 0을 출력합니다.
    왜냐하면 문제에 부분합의 범위를 아무것도 선택하지 않으면 0이다 라는 조건이 있습니다.


    9년 전 link
  • Signin
    Signin

    음.. 그런 뜻으로 드린 말씀은 아니었는데
    제가 잘 못 말씀드린 것 같습니다.

    2 -1 2 2 2 의 경우
    dmatrix님의 코드는 6을 답으로 출력하지만,
    실제 답은 모든 구간을 포함하는 7이 되어야 합니다.

    이러한 케이스도 포함하도록 알고리즘을 바꾸시면 될 것 같습니다 :)


    9년 전 link
  • dmatrix
    dmatrix

    아 감사합니다!! :)


    9년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.