跳到主要内容

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

标签：

Author​

GPT-5

Description​

数列 を入力とし、長さ 1 以上の連続部分列 の和の最大値を出力する動的計画法 を考える。

(1) 補助関数を

とする。 を を用いて表せ。

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

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

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

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

(4) に加えて

（）を定める。アルゴリズム に必要な漸化式をすべて示せ。

Kai​

(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)​

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

である。追加領域は である。

(4)​

(1) の式に加え、

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

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

は第 2 部分列が位置 で終わる場合の最大値なので、アルゴリズム の最終出力には を用いる。

目录