動的計画法で輪になった並びから隣り合わない合計を最大にする｜コーディング面接問題

問題

「隣り合わない日を選んで稼ぎを最大にする」問題の続きです。単発の仕事に入れる予定が n 日分あり、日ごとの稼ぎが並び values で決まっています。この予定は、最後の日まで終わるとまた 1 日目から同じ順に繰り返します。そのため、最後の日と次の巡りの 1 日目も、続けて働く 2 日になります。

体を休めるため、続けて 2 日は働けません。ひと巡りの中で働く日をうまく選んだとき、稼ぎの合計の最大を返す関数を書いてください。

隣り合う 2 つの日は、同時に選べません。最後の日と最初の日も隣どうしです
1 日も働かなくても構いません
values の長さは 1 以上 100 以下、値はどれも 0 以上 1000 以下の整数です
長さが 1 のときは、その 1 日を選べるものとします。自分自身とは隣どうしと見ません

入力と出力の例

例 1

輪でなければ、1 日目の 4 と 4 日目の 6 で 10 です。ただ、この 2 日は輪の上で隣どうしなので選べません。2 日目の 2 と 4 日目の 6 で 8 が答えです。

入力

values = [4, 2, 3, 6]

出力

例 2

6 日でひと巡りなので、1 日目と 4 日目は隣どうしではありません。1 日目の 5 と 4 日目の 6 で 11 です。

入力

values = [5, 1, 2, 6, 2, 3]

出力

例 3

予定が 1 日だけなら、その日を選べます。

入力

values = [7]

出力

面接での聞かれ方

面接では、まっすぐな並びの版を解いたすぐあとに、決まりを 1 つ変えて出されることが多いです。

「では、並びが輪になっていて、最初と最後も隣どうしだったらどうしますか？」
「最初と最後を両方選んでしまうのを、どう防ぎましたか？」と、場合の分け方を説明させられます
「長さが 1 のときは？」「長さが 2 のときは？」と、端の場合を続けて確かめられます

まっすぐな版の書き方を新しく作り直す必要はありません。前に書いた関数をどう使い回すかを見られています。

アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。

まず考える手順

段 1

まっすぐな並びでは、前から 1 日ずつ「選ぶ」「選ばない」の大きいほうを表に書き、前の 2 つの値だけを持ち歩きました。これを輪にそのまま当てると、最初の日と最後の日を両方選んだ答えが出ることがあります。例 1 では 10 を返してしまいます。

段 2

輪で困るのは、最初の日と最後の日の 1 組だけです。どんな正しい選び方でも、「最初の日を選ばない」か「最後の日を選ばない」の少なくとも一方は成り立ちます。最初の日を除いた並びと、最後の日を除いた並びは、どちらももう輪ではありません。まっすぐな版の解き方でそれぞれの最大を求め、大きいほうを答えにします。

段 3

両方の日を選ばない選び方は、2 本のどちらにも入っているので、別に数える必要はありません。長さが 1 のときは、どちらを除いても空になって 0 が返ってしまうので、先に分けてその日の値を返します。並びの写しを作らず、番号の範囲を渡して同じ関数を 2 回呼びます。

解答

Python

def line(values, lo, hi):
    before, best = 0, 0
    for i in range(lo, hi):
        v = values[i]
        pick = before + v
        before = best
        best = max(best, pick)
    return best


def circle_max(values):
    n = len(values)
    if n == 1:
        return values[0]
    return max(
        line(values, 0, n - 1),
        line(values, 1, n),
    )

JavaScript

function line(values, lo, hi) {
  let before = 0;
  let best = 0;
  for (; lo < hi; lo++) {
    const v = values[lo];
    const pick = before + v;
    before = best;
    best = Math.max(best, pick);
  }
  return best;
}

function circleMax(values) {
  const n = values.length;
  if (n === 1) return values[0];
  return Math.max(
    line(values, 0, n - 1),
    line(values, 1, n),
  );
}

Go

func line(values []int) int {
	before, best := 0, 0
	for _, v := range values {
		pick := before + v
		before = best
		best = max(best, pick)
	}
	return best
}

func circleMax(
	values []int,
) int {
	n := len(values)
	if n == 1 {
		return values[0]
	}
	a := line(values[:n-1])
	b := line(values[1:])
	return max(a, b)
}

line は、まっすぐな並びの版とまったく同じ中身です。Python と JavaScript は番号の範囲 (lo から hi の手前まで) を渡し、並びの写しを作りません。Go の切り出しは元の並びを指すだけで写しを作らないので、そのまま渡しています。

計算量

時間は O(n) です。長さ n - 1 の並びを 2 回なめるだけです
使う記憶は O(1) です。持ち歩くのは 2 つの変数だけで、並びの写しも作りません
最初の日を選ぶ場合と選ばない場合で表を 2 枚持つ書き方もできますが、計算量は同じで、書く量が増えます

よくある間違い

まっすぐな版をそのまま 1 回だけ呼ぶ。最初と最後を両方選んだ答えが混ざります。例 1 の [4, 2, 3, 6] で 10 を返したら、この間違いです
長さ 1 を分け忘れる。最初を除いた並びも最後を除いた並びも空になり、0 を返してしまいます。例 3 の [7] は 7 です
最初と最後の両方を除いた並びだけを使う。最初か最後のどちらかを選ぶ答えを取りこぼします。例 2 の 11 は、最初の日を選んでいます
切り出しで写しを作ったのに記憶を O(1) と言う。 Python の切り出しや JavaScript の slice は新しい並びを作るので、記憶は O(n) です。写しを作るなら、計算量もそう言います

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日

動的計画法で輪になった並びから隣り合わない合計を最大にする

問題