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

标签：

• Tokyo-University
• Maximum-Subarray-Sum

Author

zephyr

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)$。

题目描述

给定可能含负数的整数序列 $s_1,\ldots,s_n$，要求找到

$$1\le x\le y\le n$$

使连续区间和

$$\sum_{k=x}^{y}s_k$$

最大。先定义以位置 $i$ 结尾的最佳非空连续区间和

$$t_i=\max_{1\le j\le i}\left(\sum_{k=j}^{i}s_k\right).$$

1. 写出 $t_1$。
2. 用 $t_i$ 与 $s_{i+1}$ 写出 $t_{i+1}$ 的递推式。
3. 设计一个在 $O(n)$ 时间内计算
   $$\max_{1\le x\le y\le n}\left(\sum_{k=x}^{y}s_k\right)$$
   且输出一对达到最大值的端点 $(x,y)$ 的算法。假设两个整数的加法与取最大值均耗费单位时间。

考点

• 最大子数组和动态规划：在“从当前位置重新开始”和“延长前一最佳后缀”之间取优，建立 Kadane 型递推。
• 最优区间恢复：在线性扫描中同步维护当前候选左端点、全局最佳值及其左右端点，包含全负数情形。

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$$

(2)

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})$ 对于解题至关重要。

解题技巧和信息

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

重点词汇

1. subarray 子数组
2. maximum subarray sum 最大子数组和
3. dynamic programming 动态规划
4. sequence 序列

参考资料

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