티스토리 뷰

Maximum Subarray Problem을 선형 시간에 푸는 방법은 다음과 같다.

(원래 0 ~ n-1을 선호하지만, 이번에는 부분합을 써야 해서 1 ~ n으로 배열 인덱스를 설정하겠다.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int cmax = 0, res = 0, qmax = *max_element(a+1,a+n+1);
    if(qmax < 0) return qmax;
    for (int i=1; i<=n; i++) {
        cmax += a[i];
        if(cmax < 0) cmax = 0;
        res = max(res,cmax);
    }
    return res;
}
 


이 간단하고 빠른 알고리즘은, 1 ~ x 중의 Maximum Subarray라는 문제를 (1 ~ x-1 중의 Maximum Subarray, ~~ x 까지의 Maximum Subarray) 라는 두가지 부분 문제로 나누어서 문제를 해결한다는 아이디어에서 착안했다고 한다. (Dynamic programming의 일종)

하지만, 난 저걸 처음 볼때도 잘 이해가 안 갔고, 지금도 잘 이해가 안간다.

내 방식대로 유도하고자 한다.


#1. naive (n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int res = 0;
    for (int i=1; i<=n; i++) {
        int sm = 0;
        for (int j=i; j<=n; j++) {
            sm += a[i];
            res = max(res,sm);
        }
    }
    return res;
}
 




더 이상의 자세한 설명은 생략한다.


2. 부분합 사용 (n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int b[100005] = {}, res = 0;
    for (int i=1; i<=n; i++) {
        b[i] = b[i-1] + a[i];
    }
    for (int i=1; i<=n; i++) {
        for (int j=i; j<=n; j++) {
            res = max(res,b[j] - b[i-1]);
        }
    }
    return res;
}
 

부분합을 사용해서 이렇게도 표현할 수 있다. 아직은 별로 의미 없다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int b[100005] = {}, res = 0;
    for (int i=1; i<=n; i++) {
        b[i] = b[i-1] + a[i];
    }
    for (int i=1; i<=n; i++) {
        for (int j=0; j<i; j++) {
            res = max(res,b[i] - b[j]);
        }
    }
    return res;
}
 

더 간단한 표현법.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int b[100005] = {}, res = 0;
    for (int i=1; i<=n; i++) {
        b[i] = b[i-1] + a[i];
    }
    for (int i=1; i<=n; i++) {
        res = max(res,b[i] - *min_element(b,b+i));
    }
    return res;
}

이제부터 의미가 보이기 시작할 것이다.

res = max(b[i] - b[j]) 라고 할때, i를 고정시켜 놓았을때, b[j]는 0  ~ i-1 까지에서의 최솟값이라는 것을 알 수 있다.

그러면, 우리가 0 ~ 0, 0 ~ 1, 0 ~ 2까지의 최솟값을 계속 중복해서 구하고 있다는 사실이 여기서 드러난다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int b[100005] = {}, res = 0;
    for (int i=1; i<=n; i++) {
        b[i] = b[i-1] + a[i];
    }
    int minv = 0;
    for (int i=1; i<=n; i++) {
        res = max(res,b[i] - minv);
        minv = min(minv,b[i]);
    }
    return res;
}

여기까지만 해도 AC가 된다.

모든 값이 마이너스일 때의 예외처리가 필요한데, 이 부분은 생략한다.


3. 식 변형 (n)

이제 위 식을 조금 변형시키면 완전한 원래 꼴을 유도할 수 있다.

사실 저 위 식으로도 대부분의 문제는 다 풀수 있어 보이니... 이 부분은 생략해도 무방.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int res = 0;
    int minv = 0;
    int sum = 0;
    for (int i=1; i<=n; i++) {
        sum += a[i];
        res = max(res,sum - minv);
        minv = min(minv,sum);
    }
    return res;
}
 

이제는 b[i] 배열도 불필요하다. sum이라는 변수 하나만으로 모두 대체할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int res = 0;
    int sum = 0;
    int sum_minus_minv = 0;
    for (int i=1; i<=n; i++) {
        sum += a[i];
        sum_minus_minv += a[i];
        res = max(res,sum_minus_minv);
        sum_minus_minv = max(sum_minus_minv,sum-sum);
    }
    return res;
}
sum - minv 값을 저장하는 변수를 잡고, 마지막 줄을 적당히 이항시키면 이러한 식이 나온다.

sum - minv를 sum2라 하겠다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int res = 0;
    int sum = 0;
    int sum2 = 0;
    for (int i=1; i<=n; i++) {
        sum += a[i];
        sum2 += a[i];
        res = max(res,sum2);
        sum2 = max(sum2,0);
    }
    return res;
}

잘 보면 이제 sum 배열도 안 쓴다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
#include <algorithm>
using namespace std;
 
int max_sum(int *a, int n){
    int res = 0;
    int sum2 = 0;
    for (int i=1; i<=n; i++) {
        sum2 += a[i];
        res = max(res,sum2);
        sum2 = max(sum2,0);
    }
    return res;
}
끝.


댓글
  • 프로필사진 비밀댓글입니다 2016.03.24 12:36
  • 프로필사진 구사과 c++ 언어를 사용했습니다.

    이 글에서 언어는 알고리즘을 보여주는 목적으로만 사용했기 때문에, 실제로 프로그램이 컴파일되지 않을 가능성이 있습니다. (희박하지만. ) 참고해주세요.
    2016.03.25 00:54 신고
  • 프로필사진 비밀댓글입니다 2016.03.31 10:32
  • 프로필사진 비밀댓글입니다 2017.11.28 20:06
  • 프로필사진 구사과 모든 원소가 0 미만일 때 예외 처리를 했음을 가정한 거라 굳이 필요하지 않을 것 같습니다.

    이것 역시 옛날 글이라 코드에서 손 봐야 할 부분들이 조금씩 보이네요.

    응원해 주셔서 감사합니다.
    2017.12.06 03:44 신고
댓글쓰기 폼
공지사항
Total
454,711
Today
0
Yesterday
408