1편 링크: http://gall.dcinside.com/board/view/?id=programming&no=725837


  이 문제는 사실 매우 유명한 동적계획법 문제인 "Maximum Contiguous Subarray Sum" 문제와 결국 본질적으로 같은 문제이다.
  어떤 한 점을 기준으로 그 왼쪽에서 최소 합을 갖는 연속된 부분배열을 고르고, 오른쪽에서는 최대 합을 갖는 연속된 부분배열을 고르거나,
  반대로 오른쪽에서 최소합, 왼쪽에서 최대합을 구하는 것을 반복하면 필요한 모든 경우를 볼 수 있다(해당 기준점을 옮겨가면서 모든 경우를 확인하면 된다).
  포인트는 기준점이 이동했을 때, 배열 전체를 순회하지 않고 미리 계산해둔 값을 이용하는 것이다.
  이는 동적계획법으로 어떤 점 "까지의" 최대/최소 부분배열의 합, 어떤 점 "부터의" 최대/최소 부분배열의 합을 가지고 있는 것으로 간단히 해결할 수 있다.

  N = 배열의 길이라고 하면

  Additional Space Complexity는 O(N)

  Time Complexity도 O(N)이 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
unsigned distance(int x, int y) {
    if (min(x, y) >= 0 || max(x, y) < 0) {
        return unsigned(max(x, y) - min(x, y));
    } else {
        return unsigned(max(x, y)) + unsigned(-min(x, y));
    }
}
 
unsigned find_maximum_absdiff(const vector<int>& array) {
    vector<int>::size_type n = array.size();
 
    vector<vector<int>::size_type> indexes(n-1);
    iota(indexes.begin(), indexes.end(), 1);
 
    vector<int> max_subarray_until(n, array[0]);
    vector<int> min_subarray_until(n, array[0]);
    for (const auto& i: indexes) {
        max_subarray_until[i] = max({array[i], max_subarray_until[i-1] + array[i]});
        min_subarray_until[i] = min({array[i], min_subarray_until[i-1] + array[i]});
    }
 
    vector<vector<int>::size_type> indexes_reversed(n-1);
    iota(indexes_reversed.rbegin(), indexes_reversed.rend(), 0);
 
    vector<int> max_subarray_from(n, array[n-1]);
    vector<int> min_subarray_from(n, array[n-1]);
 
    for (const auto& i: indexes_reversed) {
        max_subarray_from[i] = max({array[i], max_subarray_from[i+1] + array[i]});
        min_subarray_from[i] = min({array[i], min_subarray_from[i+1] + array[i]});
    }
 
    unsigned answer = 0;
    for (const auto& i: indexes) {
        answer = max({answer,
                      distance(min_subarray_until[i-1], max_subarray_from[i]),
                      distance(max_subarray_until[i-1], min_subarray_from[i])});
    }
 
    return answer;
}
cs

연습문제1) Additional Space Complexity를 O(1)로 줄일 수 있을까요? 있다면, 어떻게 짜면 될까요?