神のみぞ知る株取引で得られる利益の最大値

# はじめに
株やFX、仮想通貨などで儲けたい！！
と考えたことはあるでしょうか？

時間によって価値が変わる取引では
**安く買い、高く売る**
戦略が大切ですよね。

今回は、株価を予測するのではなく、
**事前に株価の時系列データが手に入っている場合、
利益を最大化するためにはどのような戦略が必要なのか**
考えてみようと思います。

本記事では
**利益を最大化するためのアルゴリズム**
を様々な例題を通して理解することができます。

途中から数式に基づく解説を含みますが
わからなくなった場合は**軽く読み飛ばし**

基本問題：　２問
応用問題：　４問

の例題を通して理解を深めて頂けると幸いです。

## 目次
[1. 例題](#例題)
[2. 解答](#解答)
[3. 問題](#問題)
[4. 解法](#解法)
[5. 基本](#基本)
[6. 応用](#応用)
[7. まとめ](#まとめ)


## 例題
株価の時系列データ`prices=[1,3,2,4]`が与えられ
最大`1`回取引が可能である場合
利益の最大値`answer`はいくらか？

## 解答
1. 取引をしない場合
取引をしなければ、利益は生まれないので`0`

2. 取引をする場合
最も安い時に買って、最も高い時に売れば良いので
`- min(prices) + max(prices) = -1 + 4 = 3`
となります。
（この例のみ売買の順番を考慮しません)

3. 正解
`answer = 3`となります。

非常に簡単でしたね。
以下では、この例題を一般化することで
様々な問題を解いていきます。

## 問題
株価の時系列データ`prices`が与えられ
最大`k`回取引が可能である場合
利益の最大値`answer`はいくらか？

ただし、`prices`は長さが`n`の配列で
`0 <= i < n`を時間とみなした場合
`prices[i]`は`i`番目の株価と解釈する。

株の取引は`i`番目の時に買って
`j`番目の時に売れることにする(`i < j`)。

## 解法
さて、
**利益を最大化するためにはどのような戦略が必要** 
になるのでしょうか？

`i`番目の時間にできることを整理したいと思います。

`i`番目にできることは

- `Buy` ：株を買うこと
- `Sell` ：株を売ること
- `Rest` ：何もしないこと

です。

もう少し具体的に説明をすると、

- `Buy` ：`i-1`番目までに株を売り切っている、つまり、株を所有していない場合、株を買うこと
- `Sell` ：`i-1`番目までに株を買っている、つまり、株を所有している場合、株を売ること
- `Rest` ：何もしないこと

となります。 

次に、
`i`番目における利益を最大化する方法について場合分けします。

1. `i`番目に株を買うべき場合とは？
`i-1`番目までに株を売り切って
株を所有していない場合の利益から
株を買っても損をしない場合

2. `i`番目に株を売るべき場合とは？
`i-1`番目までに株を買って
株を所有している場合の利益から
株を売ることで得する場合

3. `i`番目に何もしないべき場合とは？
`i`番目に売買すると損する場合

となります。

それでは、

- `Buy[i]` ：`i`番目に株を買うか、何もしない場合の利益の最大値
- `Sell[i]` ：`i`番目に株を売るか、何もしない場合の利益の最大値

と定義して、
上記の場合分けについて数式的に考えましょう。

`i`番目におけるそれぞれの場合の利益の最大値は

`Buy[i] = max(Buy[i-1], Sell[i-1] - prices[i])`
`Sell[i] = max(Sell[i-1], Buy[i-1] + prices[i])`

と表すことができます。
高校数学の数列のようなものが登場してきましたね。

`i`番目と`i-1`番目の関係を利用する、
つまり、帰納的な関係を利用して問題を解くことを

**動的計画法（Dynamic Programming: DP）**と呼びます。

問題文からは予想されないような、
コンピュータサイエンスのアルゴリズム
がここで登場することになります。

一見、これで問題が解けそうに思われますが
一つ大切なことを忘れていました。

**最大`k`回取引が可能**

という制約です。

取引回数を`Buy`と`Sell`に組み込むため

- `Buy[k][i]` ：`i`番目で株を買うことができ、最大`k`回取引済みの利益の最大値
- `Sell[k][i]` ：`i`番目で株を売ることができ、最大`k`回取引済みの利益の最大値

と定義し直すことにします。

この時、`i`と`i-1`番目の関係について整理しようと思います。

- `Buy[k][i] = max(Buy[k][i-1], Sell[k-1][i-1] - prices[i])`
- `Sell[k][i] = max(Sell[k][i-1], Buy[k][i-1] + prices[i])`

と表すことができます。

だんだん複雑になってきたので、
この時点で理解が難しくてもご安心ください。
後で紹介する例題を通して理解を深めていこうと思います。

最後に、`Buy`と`Sell`の**初期値**について考えます。

`i`は`prices`のindexを表すので、
基本的には`0 <= i < n`の値をとります。

例） `prices=[1,2,3]`の場合、`p[0] = 1`である。

取引開始以前の場合を仮に`i = -1`と定義すると、

- `Buy[k][-1] = -Infinity`
- `Sell[k][-1] = 0`

となります。(`k >= 0`)

`Sell[k][-1] = 0`となるのは、
株を所有していないため確実に利益を得ることができないからです。

一方で、`Buy[k][-1] = -Infinity`となるのは、
取引初期における`i = 0`の場合

`Buy[k][0] = max(Buy[k][-1], Sell[k-1][-1] - prices[0]) = max(Buy[k][-1], 0 - prices[0])`

となるため、
確実に`Buy[k][-1] < -prices[0]`
とすることで

`Buy[k][0] = -prices[0]`とする、
つまり、最初に株を買うことで
取引の**機会**を最大化するからです。

`k = 0`の場合、つまり、取引を１度も行わない場合

- `Buy[0][i] = -Infinity`
- `Sell[0][i] = 0`

となります。(`0 <= i < n`)
これは`i = -1`と同様の理由になります。

一般的な解法の説明は以上になります。お疲れ様でした！！

ここからは例題を通して理解を深めていきます。


## 基本
### `k = 1`の場合
問題：
株価の時系列データ`prices=[1,5,4,8,3,6,2,7]`が与えられ
最大`1`回取引が可能である場合
利益の最大値`answer`はいくらか？

解答：
この問題は、一番最初の例題と同じ設定`k = 1`になります。

解法を利用して、`Sell[1]`と`Buy[1]`について考えると

- `Sell[1][i] = max(Sell[1][i-1], Buy[1][i-1] + prices[i])`
- `Buy[1][i] = max(Buy[1][i-1], Sell[0][i-1] - prices[i]) = max(Buy[1][i-1], -prices[i])`

となります。

`Sell[0][i-1] = 0`である点がポイントです。

それでは、`Sell`と`Buy`について表を使って確認しましょう。


|prices |         |1        |5        |4        |8        |3        |6        |2        |7        |
|---    |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |
|||||||||||
|Index  |-1       |0        |1        |2        |3        |4        |5        |6        |7        |
|Sell[0]|0        |0        |0        |0        |0        |0        |0        |0        |0        |
|Buy[0] |-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|
|Sell[1]|0        |0        |4        |4        |7        |7        |7        |7        |7        |
|Buy[1] |-$\infty$|-1       |-1       |-1       |-1       |-1       |-1       |-1       |-1       |

常に`Sell[k][i] > Buy[k][i]`となることに着目してください。

最後にコードで確認しましょう。

```python
def func(prices: List[float]) -> float:
    sell, buy = 0, -float('inf')
    for p in prices:
        sell = max(sell, buy + p)
        buy = max(buy, - p)
    return sell
```

正解は表で言うところの`Sell[k] = Sell[1]`の一番最後の値になるので

`answer = Sell[1][7] = 7`となります。

ちなみに、`k = 0`の場合や、`prices = [1,5]`または`prices = [1,5,4]`の場合も
表より正解を確認することができますね。

例) `k = 0`の場合は取引ができないので`answer = Sell[0][7] = 0`
例) `prices = [1,5]`の場合は`answer = Sell[1][1] = 4`
例) `prices = [1,5,4]`の場合は`answer = Sell[1][2] = 4`



### `k = Infinity`の場合
問題：
株価の時系列データ`prices=[1,5,4,8,3,6,2,7]`が与えられた場合
利益の最大値`answer`はいくらか？

解答：
この問題は、`k`に関する記述が省略されています。

`k = Infinity`の場合、

- `Sell[k][i-1] = Sell[k-1][i-1]`
- `Buy[k][i-1] = Buy[k-1][i-1]`

と考える点がポイントになります。

なぜなら、売買のタイミングが同時にならなければ、
`k`に関する制約がない、つまり、売買の回数を考慮しなくて良いためです。

解法を利用して、`Sell[k][i]`と`Buy[k][i]`について考えると

- `Sell[k][i] = max(Sell[k][i-1], Buy[k][i-1] + prices[i])`
- `Buy[k][i] = max(Buy[k][i-1], Sell[k-1][i-1] - prices[i]) = max(Buy[k][i-1], Sell[k][i-1] - prices[i])`

となります。

それでは、`Sell`と`Buy`について表を使って確認しましょう。


|prices |         |1        |5        |4        |8        |3        |6        |2        |7        |
|---    |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |
|||||||||||
|Index  |-1       |0        |1        |2        |3        |4        |5        |6        |7        |
|Sell[0]|0        |0        |0        |0        |0        |0        |0        |0        |0        |
|Buy[0] |-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|
|Sell[k]|0        |0        |4        |4        |8        |8        |11       |11       |16       |
|Buy[k] |-$\infty$|-1       |-1       |0        |0        |5        |5        |9        |9        |

最後にコードで確認しましょう。

```python
def func(prices: List[float]) -> float:
    sell, buy = 0, -float('inf')
    for p in prices:
        temp = sell
        sell = max(sell, buy + p)
        buy = max(buy, temp - p)
    return sell
```

正解は表で言うところの`Sell[k]`の一番最後の値になるので

`answer = Sell[k][7] = 16`となります。

手計算でも確認してみてくださいね。

基本問題は以上になります。

## 応用
### `k = 2`の場合
問題：
株価の時系列データ`prices=[1,5,4,8,3,6,2,7]`が与えられ
最大`2`回取引が可能である場合
利益の最大値`answer`はいくらか？

解答：
`k = 1`と同じやり方で解けるような気がしますが、
実は工夫が必要です。

解法を利用して、`Sell[k][i]`と`Buy[k][i]`を確認しましょう。

- `Sell[2][i] = max(Sell[2][i-1], Buy[2][i-1] + prices[i])`
- `Buy[2][i] = max(Buy[2][i-1], Sell[1][i-1] - prices[i])`
- `Sell[1][i] = max(Sell[1][i-1], Buy[1][i-1] + prices[i])`
- `Buy[1][i] = max(Buy[1][i-1],  -prices[i])`

それでは、`Sell`と`Buy`について表を使って確認しましょう。


|prices |         |1        |5        |4        |8        |3        |6        |2        |7        |
|---    |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |
|||||||||||
|Index  |-1       |0        |1        |2        |3        |4        |5        |6        |7        |
|Sell[0]|0        |0        |0        |0        |0        |0        |0        |0        |0        |
|Buy[0] |-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|
|Sell[1]|0        |0        |4        |4        |7        |7        |7        |7        |7        |
|Buy[1] |-$\infty$|-1       |-1       |-1       |-1       |-1       |-1       |-1       |-1       |
|Sell[2]|0        |0        |4        |4        |8        |8        |10       |10       |12       |
|Buy[2] |-$\infty$|-1       |-1       |0        |0        |4        |4        |5        |5        |

最後にコードで確認しましょう。

```python
def func(prices: List[float]) -> float:
    sell_1 = sell_2 = 0
    buy_1 = buy_2 = -float('inf')
    for p in prices:
        sell_2 = max(sell_2, buy_2 + p)
        buy_2 = max(buy_2, sell_1 - p)
        sell_1 = max(sell_1, buy_1 + p)
        buy_1 = max(buy_1, - p)
    return sell_2
```

正解は`answer = Sell[2][7] = 12`となります。

ちなみに、`Sell[1][7]`は最大`1`回取引した場合の利益の最大値なので、
基本問題と同じ値になります。

そろそろ手計算で追うことが大変になってきましたよね。

### `k = t = 3`の場合
問題：
株価の時系列データ`prices=[1,5,4,8,3,6,2,7]`が与えられ
最大`3`回取引が可能である場合
利益の最大値`answer`はいくらか？

解答：
Transaction `t`は任意の数とします。今回は`t = 3`の場合で説明します。

解法に関しては既に説明した通りです。
今回は、高速化のアプローチを一つ紹介します。

株価の時系列データ`prices`が長さ`n`の場合、
最大取引回数は`n / 2`回となります。

例) `n = 8`の場合、最大取引回数は`8 / 2 = 4`

よって、与えられたTransaction `t >= n / 2`の場合は
最大取引回数以上になるため`k = Infinity`と同じアプローチを利用可能です。

次に、`Sell`と`Buy`について表を使って確認しましょう。

|prices |         |1        |5        |4        |8        |3        |6        |2        |7        |
|---    |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |
|||||||||||
|Index  |-1       |0        |1        |2        |3        |4        |5        |6        |7        |
|Sell[0]|0        |0        |0        |0        |0        |0        |0        |0        |0        |
|Buy[0] |-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|
|Sell[1]|0        |0        |4        |4        |7        |7        |7        |7        |7        |
|Buy[1] |-$\infty$|-1       |-1       |-1       |-1       |-1       |-1       |-1       |-1       |
|Sell[2]|0        |0        |4        |4        |8        |8        |10       |10       |12       |
|Buy[2] |-$\infty$|-1       |-1       |0        |0        |4        |4        |5        |5        |
|Sell[3]|0        |0        |4        |4        |8        |8        |11       |11       |15       |
|Buy[3] |-$\infty$|-1       |-1       |0        |0        |5        |5        |8        |8        |

最後にコードで確認しましょう。

```python
def func(prices: List[float], k: int) -> float:
    if k >= len(prices) // 2:
        sell, buy = 0, -float('inf')
        for p in prices:
            temp = sell
            sell = max(sell, buy + p)
            buy = max(buy, temp - p)
        return sell

    sell, buy = [0] * (k + 1), [-float('inf')] * (k + 1)
    for p in prices:
        for i in range(k):
            sell[i] = max(sell[i], buy[i] + p)
            buy[i] = max(buy[i], sell[i + 1] - p)
    return sell[0]
```

コードに関しては、`k = 2`の場合を一般化するために
配列を使用しています。

正解は`answer = Sell[3][7] = 15`となります。

もう手計算はお腹いっぱいです。

### 条件付きの場合
問題：
株価の時系列データ`prices=[1,5,4,8,3,6,2,7]`が与えられ
株を`i-1`の時間で売った場合、`i`の時間で買うことができない場合
利益の最大値`answer`はいくらか？

解答：
株価の時系列データが非常に短期間のスパンで提供された場合、
連続した時間で株の売買ができないということも想定されるかと思います。

この問題は、`k`に関する記述が省略されているので`k = Infinity`の場合となります。

`k = Infinity`の場合との差分は以下の解法で説明します。

「`k = Infinity`の場合」

- `Sell[k][i] = max(Sell[k][i-1], Buy[k][i-1] + prices[i])`
- `Buy[k][i] = max(Buy[k][i-1], Sell[k][i-1] - prices[i])`


「今回(=条件付き)の場合」

- `Sell[k][i] = max(Sell[k][i-1], Buy[k][i-1] + prices[i])`
- `Buy[k][i] = max(Buy[k][i-1], Sell[k][i-2] - prices[i])`

今回の場合は、売買を連続して行うことができないため
`Buy[k][i]`の最後の項が

`Sell[k][i-1] - prices[i]`

から

`Sell[k][i-2] - prices[i]`

に変わっていることに注目してください。

`Sell`と`Buy`について表を使って確認しましょう。

|prices |         |1        |5        |4        |8        |3        |6        |2        |7        |
|---    |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |
|||||||||||
|Index  |-1       |0        |1        |2        |3        |4        |5        |6        |7        |
|Sell[0]|0        |0        |0        |0        |0        |0        |0        |0        |0        |
|Buy[0] |-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|
|Sell[k]|0        |0        |4        |4        |7        |7        |7        |7        |12       |
|Buy[k] |-$\infty$|-1       |-1       |-1       |-1       |1        |1        |5        |5        |

最後にコードで確認しましょう。

```python
def func(prices: List[float]) -> float:
    sell = last_sell = 0
    buy = -float('inf')
    for p in prices:
        temp = sell
        sell = max(sell, buy + p)
        buy = max(buy, last_sell - p)
        last_sell = temp
        print(sell, buy)
    return sell
```

正解は`answer = Sell[k][7] = 12`となります。

本当に出力があっているか確認してみたくださいね。

次が最後の問題になります。

### 手数料がかかる場合
問題：
株価の時系列データ`prices=[1,5,4,8,3,6,2,7]`が与えられ
毎回の取引で手数料`fee=3`がかかる場合
利益の最大値`answer`はいくらか？

解答：
最後なので、最も現実的な問題になっております。
現実の株取引では手数料は避けては通れないですよね。

なお、`k`に関する記述が省略されているので`k = Infinity`とします。

この問題では、解法が２種類あります。
その理由は、手数料が発生するタイミングを２つ定義することができるからです。

「株を買う時に手数料が発生する場合」

- `Sell[k][i] = max(Sell[k][i-1], Buy[k][i-1] + prices[i])`
- `Buy[k][i] = max(Buy[k][i-1], Sell[k][i-1] - prices[i] - fee)`

「株を売る時に手数料が発生する場合」

- `Sell[k][i] = max(Sell[k][i-1], Buy[k][i-1] + prices[i] - fee)`
- `Buy[k][i] = max(Buy[k][i-1], Sell[k][i-1] - prices[i])`

それでは、`Sell`と`Buy`について表を使って確認しましょう。

|prices |         |1        |5        |4        |8        |3        |6        |2        |7        |
|---    |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |:-:      |
|||||||||||
|Index  |-1       |0        |1        |2        |3        |4        |5        |6        |7        |
|Sell[0]|0        |0        |0        |0        |0        |0        |0        |0        |0        |
|Buy[0] |-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|-$\infty$|
|Sell[k]|0        |0        |1        |1        |4        |4        |4        |4        |6        |
|Buy[k] |-$\infty$|-1       |-1       |-1       |-1       |1        |1        |2        |2        |

最後にコードで確認しましょう。

```python
def func(prices: List[float], fee: int) -> float:
    sell, buy = 0, -float('inf')
    for p in prices:
        temp = sell
        sell = max(sell, buy + p - fee)
        buy = max(buy, temp - p)
    return sell
```

正解は`answer = Sell[k][7] = 6`となります。

手数料が発生すると最大値`answer`も小さいですね。

応用問題は以上になります。

本当にお疲れ様でした！！

## まとめ
いかがでしょうか？

一見、シンプルな問題なのですが

様々な制約の下で考察をすると、
だんだん手計算では追えないほどに複雑になることが
わかるかと思います。

そして、同じ株価の時系列データ`prices`でも
制約によっては正解の値が変わることも確認できました。
(わざと設定しました。)

今回取り上げていない場合や`prices`についても
ぜひ考察して頂きたいと思います。
例) `prices = [3,2,1]`

本記事では、**利益を最大化するためのアルゴリズム**として、
**動的計画法(Dynamic Programming: DP)**
を利用することを説明しました。

また、基本問題から応用問題まで
解法を用いることで問題が解けることを示しました。

手計算で解けないような現実世界の問題を効率よく正確に解くため
**コンピュータサイエンスを勉強する必要がある**
ということを再認識できたかなと思います。