JArchive 프로그래밍 일기

문제

연속합 백준 1912번

리뷰

입력 수열을 저장하는 배열 A[] 와, i인덱스값을 마지막으로 했을 때의 최대값을 저장하는 D [] 배열이 필요하다.

예를 들어, A = [ 1, -2, 3] 이 주어진다면,

D[0] 에는 A[0]을 마지막으로 하는 수열의 최대값이 들어간다. D[0] = 1 이 된다.

D[1] 에는 A[1] 을 마지막으로 하는 수열의 최대값이 들어간다.

[1, -2] 의 합과 [-2] 의 합 중에서 큰 것을 저장한다.

D[1] = -1 이 된다.

여기서 [1, -2 ] 의 합을 구할 때, 앞서 구한 값 D[0] 이 수열에 포함되어 있다.

다시 표현하면, D[0] + A[1] 의 합과 A[1] 을 비교하는 것과 같다.

D[2] 에는 A[2] 를 마지막으로 하는 수열의 최대값이 들어간다.

[1, -2, 3] 의 합과 [-2, 3]의 합과 [3] 의 합중에서 큰 것을 저장한다.

여기서도 [1, -2, 3] 의 합을 구할 때, 앞서 구한 D[1]의 값이 수열에 포함되어 있다.

즉, D[1] + A[2] 의 합과 A[2] 를 비교하는 것과 같다.

점화식은 아래와 같다.

D[i] = max(D[i-1] + A[i], A[i]);

D[i] 를 구한 다음에, D[i] 중에서 최대값을 찾아야 한다.

max_value 변수를 따로 둬서 최대값을 갱신하면 답을 구할 수 있다.

코드

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

int A[100002];
int D[100002];

int main(void){

    int len, num = 0;
    int i = 0;
    long long max_value = 0;

    scanf("%d", &len);

    for(i = 1; i <= len; i++){ // 인덱스 1부터 시작 
        scanf("%d", &num);
        A[i] = num;
    }

    max_value = D[1] = A[1]; // 초기화 

    for(i = 2; i <= len; i++){

        D[i] = max(D[i-1] + A[i], A[i]);

        if(max_value < D[i]) max_value = D[i];

    }

    printf("%lld", max_value);

    return 0;
}