問題
整数のnums をnums の
- 選ぶ区間は 1 つ以上の
要素を 含みます。 何も 選ばない (合計 0) は 数えません - 全部が
負の 数なら、 いちばん 大きい 1 つだけを 選んだ値が 答えになります numsの長さは 1 以上 100000 以下、 値は どれも -10000 以上 10000 以下です
入力と出力の例
例 1
4、
入力
nums = [2, -5, 4, -1, 3, -6, 1]出力
6例 2
全部が
入力
nums = [-7, -2, -9]出力
-2例 3
真ん中の -1 を
入力
nums = [5, -1, 5]出力
9面接での聞かれ方
面接では、
- 「整数の
配列で、 続いた 部分の 合計の 最大を 求めてください」 - 書き終えた
あとに 「その 区間の 始まりと 終わりの 位置も 返せますか？」と 広げて 聞かれます - 「全部負の
数だったら、 答えは どうなりますか？」と 端の 場合を 聞かれる こともあります
何も
まず
段 1
まずは
段 2
見方を
段 3
この
ここから解答です。先に自分で書いてから読むと、考え方が残ります。
解答
Python
Python
def max_run_sum(nums):
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur + x)
best = max(best, cur)
return bestJavaScript
JavaScript
function maxRunSum(nums) {
let cur = nums[0];
let best = nums[0];
const n = nums.length;
for (let i = 1; i < n; i++) {
const x = nums[i];
cur = Math.max(x, cur + x);
best = Math.max(best, cur);
}
return best;
}cur がbest が
計算量
- 時間は O(n) です。
並びを 前から 1 回なめるだけです - 使う
記憶は O(1) です。 持ち歩くのは 2 つの 数だけです。 Python で 2 つ目以降を 切り出すと 写しを 作るので、 気になる 場合は 位置で回します - 段 1 の
全部を 試す 書き方は、 かかる 時間が O(n²) になります
よく
- 一番大きい値を 0 から始める。
best = 0で始めると、 全部が 負の 数の ときに 0 を 返してしまいます。 例 2 の 答えは -2 です。 最初の 要素で始めます - 最後の
curを返す。curは「最後の 位置で 終わる 区間」の 最大でしか ありません。 例 1 では 最後の 1 で 終わる 区間の 最大は 1 で、 答えの 6 とは違います - 負の
数が 来たら区切る。 負の 要素を またいだほうが 大きくなる ことがあります。 例 3 では -1 を 含めた 9 が 答えです。 区切るか どうかは、 要素 1 つの 符号ではなく、 それまでの 合計が 負か どうかで決めます
面接での
書き始める
「区間を
全部試すと O(n²) です。 代わりに、 各位置で 終わる 区間の 最大を 前から 順に 求めます。 前までの 合計が 負なら 捨てて ここから 始め、 そうでなければ 付け足します。 これまでの 最大を 別に 覚えておけば、 1 回なめるだけで O(n) で 解けます。」
書き終えたら、
「例 1 で
たどります。 2 から 始め、 -5 では 付け足すと -3、 -5 だけなら -5 なので -3 です。 次の 4 では、 前が -3 で 負なので 捨てて 4 から 始めます。 -1 で 3、 3 で 6 と なり、 ここで 最大の 6 を 覚えます。 その あとの -6 と 1 では 6 を 超えないので、 答えは 6 です。」