アルゴリズムの問題の不明点

Question

AOJのこちらの問題の解説で理解できない部分があります。

この問題では、maxv を最大利益とすると...
maxv の初期値を適切に設定することです。Rt≤10^9 なので、最大の利益が負になることを考慮して、maxv の初期値は 10^9×(－1) 以下にする必要があります。

との説明ですが、なぜ初期値を10^9×(－1)以下とするのでしょうか？
解説してるブログや書籍ではmaxvに-2000000000を初期値としてますが、どうしてかがわかりません。

2≤n≤200,000

1≤Rt≤10^9

この制約ですと
利益が負の場合の最大は1-1000000000=で-999999999を初期値で良いと思うのですが。

Answer 1

すでにある回答の補足となりますが、、

解説してるブログや書籍ではmaxvに-2000000000を初期値としてますが、どうしてかがわかりません。

まず、上記については必要以上に考えなくて良いと思います。
解説を見てみましたが

maxv の初期値は 10^9×(－1) 以下にする必要があります。あるいは、R1－R0 を初期値としてもよいでしょう。

とあるので、初期値が -2000000000 でなければならないとは書かれていません。
※この数値は 10^9×(－1)以下 の条件を満たすので、特にツッコミを入れる必要はないと思います。
（-2000000000 である必要はありません）

次に 10^9×(－1)以下 という条件の根拠に関しては、質問者さんやohysさんのいう通り、「-999999999以下」が正しいと思います。

一方、y_waiwaiさんも「捕捉ができない」と仰っていますが、実装する上で、最終的に「-999999999」という答えが出力された時

• 実際に計算した結果の値なのか
• プログラムにバグがあり、値が更新されないまま初期値がそのまま出力されてしまっているのか

の区別がそれだけではわかりません。
なので、結果的には 10^9×(－1)以下 という条件が実装上は都合が良いかなと思います。
バグがないことを前提とすれば、-999999999 以下 あるいは、R1－R0 を初期値としてもよい と思います。

Comments

[iaduohcp]

R1－R0と-2000000000の両パターン理解しないと、この先学んでく上でつまずくと思い見過ごせなかったのですが、-2000000000の部分には執着しないで良いのですね。
ご回答を参考にこれから進めていきたいと思います。
ありがとうございました。

Answer 2

-999999999を初期値で良いと思うのですが。

もっと低い値が来たときに最小値が保持できないですね。

んで、-999999999が来たときに捕捉できないって問題もあります

Answer 3

質問者の考えている通りで間違い無いと思います。入力が

2
1000000000
1

の時 maxv が最小になるので。