東京大学新領域創成科学研究科メディカル情報生命専攻 2018年8月実施問題12

Author

Description

Let \(s_1, \ldots, s_n\) be a sequence of (possibly negative) integers. We wish to find \(x\) and \(y\) such that \(1 \leq x \leq y \leq n\) and maximize

\[ \sum_{k=x}^{y} s_k. \]

As a first step, we calculate

\[ t_i = \max_{1 \leq j \leq i} \left[ \sum_{k=j}^{i} s_k \right]. \]

(1) Write a formula for \(t_1\).

(2) Write a formula for \(t_{i+1}\) in terms of \(t_i\).

(3) Write an algorithm that calculates the following value and outputs a pair \((x, y)\) satisfying the requirements:

\[ \max_{1 \leq x \leq y \leq n} \left[ \sum_{k=x}^{y} s_k \right]. \]

The running time of your algorithm should be \(O(n)\). Assume that operations on two integers take unit time: \(a + b\), \(\max(a, b)\).

设 \(s_1, \ldots, s_n\) 为一个（可能为负数）的整数序列。我们希望找到 \(x\) 和 \(y\) 使得 \(1 \leq x \leq y \leq n\) 并且使

\[ \sum_{k=x}^{y} s_k \]

最大化。

第一步，我们计算

\[ t_i = \max_{1 \leq j \leq i} \left[ \sum_{k=j}^{i} s_k \right]. \]

(1) 写出 \(t_1\) 的公式。

(2) 写出 \(t_{i+1}\) 的公式。

(3) 写出一个算法计算以下值并输出满足要求的 \((x, y)\) 对：

\[ \max_{1 \leq x \leq y \leq n} \left[ \sum_{k=x}^{y} s_k \right]. \]

算法的运行时间应为 \(O(n)\)。假设对两个整数的操作需要单位时间：\(a + b\), \(\max(a, b)\)。

Kai

(1)

The formula for \(t_1\) is simply the first element of the sequence since it represents the maximum subarray sum ending at the first position:

\[ t_1 = s_1 \]

To derive \(t_{i+1}\) from \(t_i\), consider the subarray ending at position \(i+1\). There are two possibilities: either the subarray includes only \(s_{i+1}\) or it includes the subarray ending at \(i\) extended by \(s_{i+1}\). Thus:

\[ t_{i+1} = \max(t_i + s_{i+1}, s_{i+1}) \]

This formula captures the choice between starting a new subarray at \(i+1\) or extending the previous subarray to include \(s_{i+1}\).

(3)

The algorithm calculates the maximum subarray sum and identifies the starting and ending indices of the subarray that achieves this sum. Here is the algorithm in Python:

def max_subarray_sum(sequence):
    max_sum = current_sum = sequence[1]
    start = end = temp_start = 1

    for i in range(2, len(sequence) + 1):
        if current_sum > 0:
            current_sum += sequence[i]
        else:
            current_sum = sequence[i]
            temp_start = i

        if current_sum > max_sum:
            max_sum = current_sum
            start = temp_start
            end = i

    return start, end, max_sum

# Example usage
sequence = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
start, end, max_sum = max_subarray_sum(sequence)
print(f"Maximum subarray sum: {max_sum}")
print(f"Start index: {start}, End index: {end}")

Explanation

The algorithm initializes the variables max_sum, current_sum, start, end, and temp_start to keep track of the maximum subarray sum and its indices.
It iterates through the sequence, updating the current_sum based on the formula \(t_{i+1} = \max(t_i + s_{i+1}, s_{i+1})\).
If the current_sum is greater than the max_sum, it updates the max_sum, start, and end indices.
The algorithm returns the start, end, and max_sum values.

Complexity Analysis

Time Complexity: The algorithm has a time complexity of \(O(n)\) since it iterates through the sequence once.
Space Complexity: The space complexity is \(O(1)\) since the algorithm uses a constant amount of space for variables.

Knowledge

动态规划最大子序列和

难点思路

难点在于理解如何通过比较当前元素和当前子序列和来决定是否开始一个新的子序列或继续当前子序列。理解动态规划的状态转移方程 \(t_{i+1} = \max(t_i + s_{i+1}, s_{i+1})\) 对于解题至关重要。

解题技巧和信息

动态规划是一种通过分解问题并利用子问题解的技巧。对于本问题，关键在于理解如何通过前一步的解来更新当前解。
对于最大子序列和问题，Kadane's Algorithm 是一个经典解法，其时间复杂度为 \(O(n)\)，适合处理大规模数据。

重点词汇

subarray 子数组
maximum subarray sum 最大子数组和
dynamic programming 动态规划
sequence 序列

参考资料

Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, Chapter 4: Divide-and-Conquer (Maximum Subarray Problem)
The Art of Computer Programming, Volume 3: Sorting and Searching by Donald E. Knuth, Section 5.3.2: Maximum Subarray Problem

東京大学 新領域創成科学研究科 メディカル情報生命専攻 2018年8月実施 問題12