JArchive 프로그래밍 일기

문제

연속합2 백준 13398번

리뷰

연속합 문제를 풀고나서 2가 있길래 풀어봤는데, 어려웠다. 혼자서 2시간 매달려도 안되서 다른 분들의 풀이 포스팅을 읽어봤다.

주어진 수열 그대로인 경우, 수를 하나 제거하는 경우를 나눠서 2차원 배열로 관리하는 것이 핵심이었다.

처음에는 잘 이해가 안됬었다.

주어진 수열 그대로에서 연속합을 구하는 것은 D[n] [0]에서 한다.

코드

#include <stdio.h>
#include <algorithm>
using namespace std;

int N;
int A[100001];
int D[100001][2];
int max_value;

int main()
{
    int num, i = 0; 

    scanf("%d", &N);

    for(i = 1; i <= N; i++){
        scanf("%d", &num);
        A[i] = num;
    }

    D[1][0] = D[1][1] = A[1];

    max_value = max(D[1][0], D[1][1]);

    for (i = 2; i <= N; i++)
    {
        D[i][0] = A[i] +max(0, D[i-1][0]);
        D[i][1] = max(D[i-1][1] + A[i], D[i-1][0]);
        max_value = max( max(D[i][0], D[i][1]), max_value );
    }

    printf("%d", max_value);
}

참고한 포스팅