JUNGOL 실력키우기 1836 : 연속부분합 찾기

N개의 정수를 담고 있는 배열이 주어졌을 때, 여기서 가능한 연속 부분합을 구하는 프로그램을 작성하라.

 

여기서 연속 합이라는 것은 배열에서 연속된 숫자들을 선택해서 합하였을 때의 값을 말한다. 

아무 배열도 택하지 않는 경우도 연속된 배열합에 포함됨을 유의하자.

 

입력의 첫 번째 줄에는 정수 N(1≤N≤105)가 입력된다. 그리고 그 다음 줄에는 N개의 배열에 담긴 숫자가 순서대로 입력된다. 
숫자의 범위는 -100이상 100이하의 정수다.

입력에 대한 가장 큰 연속 부분합을 출력한다.

4 1 2 -2 4

5

---

단순하게 생각하면 최소일 때 원소의 개수가 1개인 부분집합에서 최대일 때 원소의 개수가 모든 원소인 부분집합의 합 중 최댓값을 찾는 문제인 것 같습니다. 그렇다면 일단 입력을 배열(혹은 벡터 등)에 저장한 뒤 1개에서 최대 개수가 될 때 까지 더한 합을 비교하면 될 것 같습니다.

실행 결과, 5개는 통과하지만 나머지 5개가 시간 초과가 되는군요. 그렇다면 속도를 어떻게 빠르게 만들지 고민 해 봐야할 것 같습니다.

#include <iostream>
 
using namespace std;
 
int GetMaxByInterval(int* arr, int n, int interval);
 
int main()
{
    int n;
 
    cin >> n;
    int *arr = new int[n];
 
    // 입력되는 원소들을 저장한다.
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    // 각 간격 별 최댓값을 구해 전체 간격 중 가장 큰 값을 찾는다.
    int totalMax{ -2100000000 };
    for (int i = 1; i <= n; ++i)
    {
        int currentMax{ GetMaxByInterval(arr, n, i) };
        if (totalMax < currentMax)
        {
            totalMax = currentMax;
        }
    }
    
    cout << totalMax << endl;
 
    delete[] arr;
}
 
// 간격 별 최댓값을 구해 리턴하는 함수
int GetMaxByInterval(int* arr, int n, int interval)
{
    int maxSum{ -2100000000 };
    
    // 더해지는 값이 배열 범위를 넘지 않을 때 까지만 계산한다.
    for (int i = 0; i <= n - interval; ++i)
    {
        int maxTemp{ 0 };
        for (int j = i; j < i + interval; ++j)
        {
            maxTemp += arr[j];
        }
        // 현재 최대 값과 비교하여 더 크다면 해당 값을 저장한다.
        if (maxSum < maxTemp)
        {
            maxSum = maxTemp;
        }
    }
 
    return maxSum;
}

생각 해 보니 전체를 다 돌 필요가 없네요. 가장 큰 값을 찾는 것이니까 커지는 경우만 계산하면 될 것 같습니다.

만약 입력 전체가 음수인 경우엔 가장 작은 음수가 최대 값이 될 것이고,

음수와 양수가 섞인 경우라면 커지는 경우에 더하면 대부분은 정답을 찾을 수 있겠네요.

그런데 예제와 같은 경우에는 값이 작아져도 전부 더했을 때 값이 더 커지는데 이 경우는 잘 생각해 보면

그 전까지 더한 값이 음수가 되는 순간 뭔 짓을 해도 최댓값이 될 수 없습니다.

위 예제에서 1 2 -3 4 인경우 그대로 더해 최댓값이 4가 될 수 있습니다.

그런데 음수가 되는 순간 1 2 -4 4 모든 값을 더해도 결과는 3이되며 최댓값인 4가 될 수 없습니다.

즉, 값이 항상 커지는 경우 더하는 변수와 값이 0 이상일 경우 더하는 변수를 따로 두고 최댓값을 구하면 됩니다.

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n;
 
    cin >> n;
 
    int totalMax{ -1000 }; // 최종 결과가 될 변수
    int greaterSum{ 0 }; // 커지는 경우 더할 변수
    int allSum{ 0 }; // 0보다 크면 더하는 변수
    
    // 입력되는 원소들을 저장한다.
    for (int i = 0; i < n; ++i)
    {
        int val;
        cin >> val;
 
        // 입력된 값이 0이상이면 항상 max가 커지므로 더한다.
        if (val >= 0)
        {
            greaterSum += val;
            allSum += val;
        }
        else
        {
            // 입력된 값이 0보다 작은 경우 작아지므로 초기화한다.
            greaterSum = 0;
            // 0보다 작아지지 않은 경우 더 커질 가능성이 있으므로 더한다.
            if (allSum + val > 0)
            {
                allSum += val;
            }
            // 음수가 된 경우 max가 될 수 없으므로 초기화한다.
            else
            {
                allSum = 0;
            }
        }
 
        // 최댓값을 저장한다.
        totalMax = max(max(greaterSum, allSum), totalMax);
    }
 
    cout << totalMax << endl;
}

JUNGOL) 문제은행) 실력키우기) 연속부분합 찾기