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일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.