東京工業大学 情報理工学院 数理・計算科学系 2018年8月実施 午前 問8

标签：

• TITech
• Maximum-Subarray-Sum
• Algorithm-Complexity

Author

GPT-5

Description

数列 $a_1,\ldots,a_n$ を入力とし、長さ 1 以上の連続部分列 $a_s,\ldots,a_t$ の和の最大値を出力する動的計画法 $A$ を考える。

(1) 補助関数を

$$f(0)=-\infty, \qquad f(t)=\max_{1\leq s\leq t}\sum_{x=s}^t a_x$$

とする。$f(m+1)$ を $f(m)$ を用いて表せ。

(2) (1) の式を使ったアルゴリズム $A$ の擬似コードを示せ。

(3) (2) のアルゴリズムの時間計算量を求めよ。

次に、互いに重ならない二つの空でない連続部分列の和

$$\max_{1\leq s\leq u<w\leq t\leq n} \left(\sum_{x=s}^u a_x+\sum_{x=w}^t a_x\right)$$

を出力する動的計画法 $B$ を考える。

(4) $f$ に加えて

$$g(t)=\max_{1\leq s\leq u\leq t}\sum_{x=s}^u a_x,$$

$$h(t)=\max_{1\leq s\leq u<w\leq t} \left(\sum_{x=s}^u a_x+\sum_{x=w}^t a_x\right)$$

（$f(0)=g(0)=h(0)=h(1)=-\infty$）を定める。アルゴリズム $B$ に必要な漸化式をすべて示せ。

题目描述

输入数列 $a_1,\ldots,a_n$，考虑动态规划算法 $A$：它输出所有长度至少为 $1$ 的连续子数组 $a_s,\ldots,a_t$ 中最大的元素和。

1. 定义辅助函数

   $$f(0)=-\infty,\qquad f(t)=\max_{1\leq s\leq t}\sum_{x=s}^t a_x.$$

   用 $f(m)$ 表示 $f(m+1)$。

2. 使用第 1 问的递推式，写出算法 $A$ 的伪代码。

3. 求第 2 问算法的时间复杂度。

接着考虑动态规划算法 $B$，它输出两个互不重叠、均非空的连续子数组之和的最大值：

$$\max_{1\leq s\leq u<w\leq t\leq n} \left( \sum_{x=s}^u a_x+\sum_{x=w}^t a_x \right).$$

4. 除 $f$ 外再定义

   $$g(t)=\max_{1\leq s\leq u\leq t}\sum_{x=s}^u a_x,$$
   $$h(t)= \max_{1\leq s\leq u<w\leq t} \left( \sum_{x=s}^u a_x+\sum_{x=w}^t a_x \right),$$

   并规定

   $$f(0)=g(0)=h(0)=h(1)=-\infty.$$

   写出实现算法 $B$ 所需的全部递推式。

考点

• 最大连续子数组动态规划：区分“必须以当前位置结尾”的最优值 $f$ 与“前缀内任意位置结束”的最优值 $g$。
• 双区间状态设计：判断第二段在当前位置开始、延长或不使用当前位置等情形，建立 $h$ 的完整转移。
• 算法复杂度：用常数时间状态更新替代枚举端点，分析一次线性扫描的时间与存储开销。

Kai

(1)

$m+1$ で終わる最適部分列は、$a_{m+1}$ だけを取るか、$m$ で終わる最適部分列を $a_{m+1}$ まで延長するかのいずれかである。従って

$$\boxed{f(m+1)=\max\{a_{m+1},f(m)+a_{m+1}\}}.$$

(2)

max_subarray(a[1..n]):
    ending = -infinity
    answer = -infinity

    for t = 1 to n:
        ending = max(a[t], ending + a[t])
        answer = max(answer, ending)

    return answer

(3)

各要素について定数回の加算と比較だけを行うため、時間計算量は

$$\boxed{O(n)}$$

である。追加領域は $O(1)$ である。

(4)

(1) の式に加え、

$$\boxed{g(m+1)=\max\{g(m),f(m+1)\}}$$

である。また $m+1$ で終わる第 2 部分列について、既存の第 2 部分列を延長する場合と、$a_{m+1}$ から新しく開始して $1,\ldots,m$ 内の最適な第 1 部分列と組み合わせる場合を比較して

$$\boxed{h(m+1)=\max\{h(m)+a_{m+1},g(m)+a_{m+1}\}}$$

を得る。従って必要な式はまとめて

$$\boxed{\begin{aligned} f(m+1)&=\max\{a_{m+1},f(m)+a_{m+1}\},\\ g(m+1)&=\max\{g(m),f(m+1)\},\\ h(m+1)&=\max\{h(m)+a_{m+1},g(m)+a_{m+1}\}. \end{aligned}}$$

$h(t)$ は第 2 部分列が位置 $t$ で終わる場合の最大値なので、アルゴリズム $B$ の最終出力には $\max_{2\leq t\leq n}h(t)$ を用いる。