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

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2556&sca=50&page=22

 Input 

10

4 5 -10 3 4 -7 -2 8 -6 -1

 

 Output 

10

* 대부분의 원형 문제는 직선으로 바꾸어 해결할 수 있다.

직선 구간에서 연속 구간의 최대합을 구하는 것은 DP를 이용해 빠르게 구할 수있습니다

 

원형으로 이루어져 있기에 해가 나올 수 있는 부분은 2가지 입니다.

① 중간 부분의 연속된 합 (DP로 빠르게 구할 수 있음)

② 끝 지점과 시작 시점이 포함되는 영역

즉, 직선에서의 연속구간 최대합은  ①만 고려해주면 되지만

원형이기 때문에 ②도 고려해주어야 합니다. 

▶ ①과 ② 중 더 큰 값이 원형구간에서 최대값이 됩니다.

 

Q. 시작과 끝이 포함되는 영역에서 최대값은 어떻게 구할까?

▶ 전체합 - 연속 부분의 최소합

먼저, 중간영역에서 연속 구간 최대합을 구했듯이 

        기존 원소의 부호를 반대로해서 최대합을 구하면 됩니다. 

        → msum (음수로서 절대값이 가장 큰 부분의 합)

그 후, 전체 합 total에서 msum 부분을 제거합니다. 

        → total - msum 

* 단, 예외 케이스는 모두 원소가 음수인 경우입니다.

ex) arr = [-1, -2, -3]은 전체 합(total) = -6 

      중간 부분에서 음수로서 절대값이 가장 큰 영역의 합(msum) = -6

      결국, -6 - (-6) = 0이 되기 때문에 이러한 경우는 제외해야 합니다.

      실제 연속구간 최대합 = -1

 

※ 연속 구간 최대합

- 배열 A[]에 0 이하의 수만 들어오는 경우 → 최대값 1개가 답이 됩니다.

- 배열 A[] 음수가 없는 경우 → 전체 합이 답이 됩니다.

---

#include<iostream>
 
using namespace std;
typedef long long LL;
const int LM = 1 << 21; // 2의 21제곱
int N, arr[LM];
LL ans = -(LL)9e9, sum, invAns, total;
 
int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
        total += arr[i];
    }
 
 
    sum = 0; // 중간 영역에서 최대합
    for (int i = 0; i < N; i++) {
        if (sum > 0) sum += arr[i];
        else sum = arr[i];
        if (ans < sum) ans = sum;
 
    }
 
    //음수절대값 합의 최대값구하기
    sum = 0;
    for (int i = 0; i < N; i++) {
        arr[i] = -arr[i];
        if (sum > 0)sum += arr[i];
        else sum = arr[i];
        if (invAns < sum) invAns = sum;
 
    }
 
    LL msum = total + invAns;
    if (msum) { //모든 원소가 음수인 경우 제외
        if (ans < msum) ans = msum;
    }
 
    printf("%lld\n", ans);
}