跳到主要内容

京都大学 情報学研究科 通信情報システム専攻 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

目录