문제

13398번: 연속합2

풀이

연속합 문제에서 한가지 조건이 추가된 문제입니다. 연속합 문제 풀이를 응용하여 이번 문제를 해결할 수 있습니다.

입력으로 주어진 배열이 arr이라 할때,
연속합 문제는 currentMax[i] = max(currentMax[i-1] + arr[i], arr[i])로 currentMax 배열을 만들어 그 중 가장 큰 값을 선택하면 되었습니다. (혹은 totalMax 배열을 만들어 전체 최대값을 저장한 후 totalMax[n-1]을 출력)

이번문제는 비교할 요소가 하나 늘었는데요
currentMax는 제외한 숫자가 없는 경우에서 현재 큰 수에 해당하니
배열 중 숫자를 하나 제거했을 때의 현재 큰 수도 저장할 필요가 있습니다.

excludeMax배열을 만들어 excludeMax[i] = max(currentMax[i-1], excludeMax[i-1]+arr[i])를 저장합니다.

• currentMax[i-1]: i번째 수가 빠진 경우
• excludeMax[i-1]+arr[i] : i번째 수 이전에 이미 빠진 수가 있는 경우

위의 두 경우를 비교하여 더 큰 수를 excludeMax 배열에 저장합니다.

이제 마지막으로 최종 가장 큰 수를 찾기 위해 currentMax와 excludeMax 배열을 비교하여 그중 가장 큰 수를 찾습니다.

코드

#include <iostream>
#include <vector>

using namespace std;

int max(int a, int b) { return a > b ? a : b; }
int max(int a, int b, int c) { return max(a, max(b, c)); }

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> arr(n);
    vector<int> currentMax(n, 0);
    vector<int> exclude(n, 0);
    for (int i=0; i<n; ++i)
        cin >> arr[i];

    currentMax[0] = arr[0];
    exclude[0] = arr[0];

    for (int i=1; i<n; ++i)
    {
        currentMax[i] = max(currentMax[i-1] + arr[i], arr[i]);
        //i번째 수가 빠진경우, i번째 수 전에 다른 수가 먼저 빠져있는 경우, a[i] 중 가장 큰 수를 저장
        exclude[i] = max(currentMax[i-1], exclude[i-1]+arr[i], arr[i]);
    }

    int maxVal = INT32_MIN;
    for (int i=0; i<n; ++i)
        maxVal = max(maxVal, currentMax[i], exclude[i]);

    cout << maxVal << endl;
    return 0;
}