【競プロ】株の売り買い問題総まとめ - Qiita

のようになります．基本的なルールは以下のようなものです． 各時刻で買う操作と売る操作のどちらかを行うことができる（何もしなくても良いが両方同時刻にはできない）． 買う前に売ることはできない 買う操作と売る操作は交互にしなければならない（買う→売る→買う→売る...としなければいけない）． ある時刻に株を買えばその時刻での株価が持ち金から引かれ，ある時刻に株を売ればその時刻での株価分のお金を得ることができる． 最初の持ち金は0．持ち金は0以下になってもよい． 最終的な持ち金の額を最大化したい． あらかじめ各時刻の値段がわかっていればすぐ計算できそう感じもしますが，問題が複雑になればそう簡単にはいきません．条件の違いによって様々なパターンがあるので，この記事ではそれを一挙に紹介します． Case 1: 1回だけ売り買いできる場合 まず，最も基本的な場合として，買う操作と売る操作を1度ずつしかで