京都大学 情報学研究科 通信情報システム専攻 2017年8月実施 専門基礎B [B-7]

Author

祭音Myyura

Description

最大連続部分和問題とは、与えられた 個の整数 に対し、最大の連続部分和を求める問題である。 すなわち、 から までのすべての要素の和を

と記したとき、 が最大となるような整数 と （ただし、）を求める問題である。 本設問では、すべての と に対して、部分和 の絶対値が で抑えられる（すなわち、）と仮定する。 ただし、 は に依存しない定数である。以下のすべての問に答えよ。

(1) 以下の表は のときの入力の例である。 この例において が最大となるような整数 と （ただし、）を求めよ。

(2) 任意の整数 が与えられたとき、部分和 が最大となるような と を求める問題を考える。 この問題を 時間で解くアルゴリズムを与えよ。

(3) 分割統治法及び (2) のアルゴリズムを用いて、最大連続部分和問題を 時間で解くアルゴリズムを与えよ。

(4) 任意の に対し、 の最大値（ただし、）を と表す。任意の に対し、

が成立することを示せ。この関係式に基づき、最大連続部分和問題を 時間で解くアルゴリズムを与えよ。

Kai

(1)

(2)

The idea is simple, find the maximum sum starting from mid point () and ending at some point on left of mid, then find the maximum sum starting from mid + 1 and ending with some point on right of mid + 1. Finally, combine the two and return the maximum among left, right and combination of both.

def max_crossing_sum(A, s, t, k):
    # 1. mid to left
    current_sum = 0
    max_left_sum = -10000
    for i in range(k, s - 1, -1):  # for i = k to s:
        current_sum += A[i]
        if current_sum > max_left_sum:
            max_left_sum = current_sum
    
    # 2. mid to right
    current_sum = 0
    max_right_sum = -10000
    for i in range(k, t + 1):  # for i = k to t:
        current_sum += A[i]
        if current_sum > max_right_sum:
            max_right_sum = current_sum
    
    return max(max_left_sum + max_right_sum - A[k], max_left_sum, max_right_sum)

Obviously, the time complexity

(3)

The algorithm can be described as follows:

• Divide the given array in two halves
• Return the maximum of following three
  • Maximum subarray sum in left half (Make a recursive call)
  • Maximum subarray sum in right half (Make a recursive call)
  • Maximum subarray sum such that the subarray crosses the midpoint (Algorithm in (2))

def max_subarray_sum(A, s, t):
    if s > t:
        return -10000
    
    if s == t:
        return A[s]
    
    k = (s + t) // 2
    return max(max_subarray_sum(A, s, k - 1),
               max_subarray_sum(A, k + 1, t),
               max_crossing_sum(A, s, t, k))

The time complexity is

(4)

represents the subarray with the largest sum ending at .

The calculation of can be divided into two cases.

If the sum of maximum subarray ending at is negative, then it should be discarded and hence .

If the sum of maximum subarray ending at is positive, then it should be included in the maximum subarray ending at and hence .

Combining the two cases we have

and the maixmum subarray sum is

The algorithm is described as follows:

def max_subarray_sum(A, n):
    dp = [0] * n
    dp[0] = A[0]
    ans = dp[0]

    for i in range(1, n):
        dp[i] = max(A[i], A[i] + dp[i-1])
        ans = max(ans, dp[i])
    
    return ans

Obviously, the time complexity is