연속된 부분 합(연속합) - 3 (DP)

※ 구간합을 구하는 효율적인 방법

연속된 부분 합(연속합) - 1 (완전 탐색) 

연속된 부분 합(연속합) - 2 (Prefix Sum)

연속된 부분 합(연속합) - 3 (DP)  

[구간합] Sum of sub-matrix (2D Array) 

DP

① D[i] = 인덱스 i를 오른쪽 끝으로 갖는 연속 구간의 최대값

② D[i - 1] > 0인 경우는 활용하지만 D[i-1] ≤ 0 이라면 이용하지 않습니다.

    partialSum = Math.max(partialSum, 0) + A[i];

    answer = Math.max(answer, partialSum);

즉, 배열을 순회하며 부분합이 0보다 작으면 이전의 부분 배열의 합은 무시하고 다시 순회한다고 보면됩니다.

(※ patialSum = D[i] / answer = D[i] 중 최대값)

[예시 코드] - O(N)

int ans = 0;
int N, A[LM], D[LN];
void findPartialSum(){
    int i;
    for(i=1; i<=N; i++){
        D[i] = A[i];
        if(D[i-1] > 0) D[i] ++ D[i-1];
    }
}

 

D[i]를 sum으로 바꾸어서 별도 배열을 만들지 않고도 구현 가능

※ D[i]와 동일하게 sum = i번째 수를 마지막으로 하는 연속 부분합의 최대값

int N, ans = 0;
void findPartialSum(){
    int i, a, sum =0;
    for(i=1; i<=N; i++){
        scanf("%d", &a);

        if(sum > 0) sum += a;
        else sum = a;
        if(ans < sum) ans = sum;
    }
}

 

Reference

- 연속된 부분 합(연속합) - 1 (완전 탐색) 

- 연속된 부분 합(연속합) - 2 (Prefix Sum)

- 연속된 부분 합(연속합) - 3 (DP)  

- [구간합] Sum of sub-matrix (2D Array) 

 

관련 문제

★ [Jungol] 3706 합이 0이 되는 연속구간 세기

- [BOJ] 10211 Maximum Subarray

- [Jungol] 3136 const 구간의 합 구하기(2D)

- [Jungol] 1836 연속부분합 찾기

- [Jungol] 3263 연속구간최대합(Circular)

- [Jungol] 3429 로봇

- [BOJ] 2470 두 용액

- [SWEA] 3819 최대 부분 배열