隣り合う日を選ばずに合計を最大にする｜コーディング面接問題

問題

単発の仕事に入れる日の予定があり、日ごとにもらえる稼ぎが並び values で決まっています。ただし体を休めるため、続けて 2 日は働けません。働く日をうまく選んだとき、稼ぎの合計の最大を返す関数を書いてください。

隣り合う 2 つの日を、同時に選ぶことはできません。1 日おきでも、何日か空けても構いません
1 日も働かなくても構いません。values が空なら 0 を返します
values の長さは 0 以上 100 以下、値はどれも 0 以上 10000 以下の整数です

入力と出力の例

例 1

2 日目の 10 と 5 日目の 9 を選ぶと 19 です。1 日目、3 日目、5 日目の 3 日を選ぶ 16 より大きくなります。

入力

values = [3, 10, 4, 2, 9]

出力

例 2

両端の 5 と 5 を選びます。1 日おきに選ぶだけが答えとは限りません。

入力

values = [5, 1, 1, 5]

出力

例 3

予定が 1 日も無ければ、稼ぎは 0 です。

入力

values = []

出力

面接での聞かれ方

面接では、場面を変えて出されることが多いです。日ごとの稼ぎのほか、並んだ家や席のように「隣どうしは選べない」形で渡されます。

「整数の配列から、隣り合わないように選んだ合計の最大を求めてください」
書き終えたあとに「どの日を選んだかも返せますか？」と広げて聞かれます
「並びが輪になっていて、最初と最後も隣どうしだったら？」と、決まりを変えて聞かれることもあります

値に負の数が無いか、何も選ばない場合を認めるかを、最初に確かめておきます。

まず考える手順

段 1

まずは素直に、選び方を全部試す方法を考えます。各日を選ぶか選ばないかで分かれるので、n 日なら 2 の n 乗通りあります。隣り合う選び方を除いて合計を比べれば正しく解けますが、100 日だと数え切れない量になります。

段 2

前から 1 日ずつ答えを決める表を考えます。「最初の i 日だけで選んだときの合計の最大」を表に書きます。i 日目について、選ばないなら答えは「i - 1 日目までの最大」のまま、選ぶなら前の日は選べないので「i - 2 日目までの最大」に i 日目の稼ぎを足した数です。この 2 通りの大きいほうを表に書きます。

段 3

表を埋めるのに使うのは、すぐ前の 2 つの欄だけです。なので表全体を持たず、「1 日前までの最大」と「2 日前までの最大」の 2 つの変数を持ち歩けば足ります。空の並びでは、どちらも 0 のまま終わるので、そのまま 0 が答えになります。

ここから解答です。先に自分で書いてから読むと、考え方が残ります。

解答

Python

def no_adjacent_max(values):
    before, best = 0, 0
    for v in values:
        pick = before + v
        before = best
        best = max(best, pick)
    return best

JavaScript

function noAdjacentMax(values) {
  let before = 0;
  let best = 0;
  for (const v of values) {
    const pick = before + v;
    before = best;
    best = Math.max(best, pick);
  }
  return best;
}

best が「1 日前までの最大」、before が「2 日前までの最大」です。pick は「今日を選ぶ」場合、best のままが「今日を選ばない」場合で、その大きいほうを新しい best にします。

計算量

時間は O(n) です。並びを前から 1 回なめるだけです
使う記憶は O(1) です。持ち歩くのは 2 つの変数だけです
段 2 の表をそのまま持つ書き方は、時間は同じ O(n) で、記憶は O(n) です。段 1 の全部を試す書き方は、時間が O(2ⁿ) です

よくある間違い

1 日おきの 2 通りだけを比べる。偶数番目の合計と奇数番目の合計を比べるだけでは足りません。例 2 の [5, 1, 1, 5] では、2 日空けて両端を選ぶ 10 が答えです
大きい日から欲張って選ぶ。一番大きい日を先に選ぶと、その両隣が使えなくなります。両隣の合計のほうが大きいこともあるので、必ず 2 通りを比べます
変数を書き換える順を間違える。 before を先に書き換えてしまうと、今日を選ぶ場合の計算に、1 日前の値が混ざります。今日を選ぶ合計を先に pick に取っておいてから、2 つを書き換えます

面接での話し方の例

書き始める前に、方針を短く口に出します。

「選び方を全部試すと 2 の n 乗通りなので、前から 1 日ずつ答えを決めます。各日で、選ばないなら前の日までの最大、選ぶなら 2 日前までの最大に今日の稼ぎを足した数で、大きいほうを取ります。使うのは前の 2 つだけなので、変数 2 つで O(n) 時間、O(1) 記憶です。」

書き終えたら、例を 1 つ手でたどって見せます。

「例 1 でたどります。1 日目は 3、2 日目は 3 と 10 を比べて 10、3 日目は 10 と 3 足す 4 の 7 を比べて 10 のままです。4 日目は 10 と 10 足す 2 で 12、5 日目は 12 と 10 足す 9 の 19 を比べて 19 です。」

面接の最後には、書いた解き方を短く振り返ります。

「表を埋める考え方を、前の 2 つだけを持つ形まで縮めました。輪になった場合も、最初の日を除いた並びと最後の日を除いた並びで同じ関数を 2 回呼べば解けると思います。時間が残っていれば、選んだ日を返す形にも直せます。」

ここまで、文字列から動的計画の入口まで、面接でよく出る型を順に練習してきました。本番では、正しく書くことと同じくらい、考えた道すじを口に出して伝えることが大切です。

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