python アルゴリズム　メモ！

忘れることが多いので、自分のメモとして残しておきます。


#1. 最大和問題

新しくarrayという配列を用意して、最大値をその配列に入れていく。基本的には、1個前と1個前の値に配列の要素を足してみて大きい方を選んでいく感じ。




```math
array[i+1] = max(array[i], array[i]+list1[i])\\

\\
array[0]=0

```


```.py
list1 = [3,-4,5,6]
N = 4

def func_max_sum(N,list1):
    array = [0]*(N+1)
    for i in range(N):
        array[i+1] = max(array[i], array[I]+list1[i])
    return array

print(func_max_sum(N,list1))
```

```.py

# array の挙動
[0, 3, 0, 0, 0]
[0, 3, 3, 0, 0]
[0, 3, 3, 8, 0]
[0, 3, 3, 8, 14]
```

### Tips
この初期化は、pythonの内包表記より早いようです。

```.py
array = [0]*(N+1)
# [0,0,0,0,0]
```





#2. 尺取り法

簡単に言うと、、、
**条件を満たすような区間をすべて求めることができる方法**
です。

全探索で考えようとすると $O(N\^2)$ の計算量ですが、
尺取り法だと $O(N)$ で出来ます。
以下の例は、整数K以下で連続する部分列のうち、最も長いものの長さを求めています。

```.py

right = 0
left = 0
total = 1
max_len = 0

list1 = [4,1,7,2]
K = 6
n = 4

while right < n :
    if total*list1[right] <= k:
        total = total*list1[right]
        right = right+1
        max_len = max(max_len, right-left)

    elif right == left:
        right = right+1
        left = left+1
    
    else:
        total //= list1[left]
        left = left+1

print(max_len)

```

###解説１
```.py
    if total*list1[right] <= k:
        total = total*list1[right]
        right = right+1
        max_len = max(max_len, right-left)
```
totalに次の要素をかけて、それがK以下の場合の処理。
K以下だったら、`right` を右にひとつ動かす。
あとは、`max_len` の更新処理。


###解説２
```.py
    elif right == left:
        right = right+1
        left = left+1
```
ここの処理は、`right` も `left` も同じ位置になったらどっちもひとつずらしましょう!ってだけ


###解説３
```.py
    else:
        total //= list1[left]
        left = left+1
```
この処理は、整数kを超えた場合一番左の値で割って値を小さくしましょう！っていう処理

#3. 累積和

適切な前処理をしておけば、配列のある区間の総和を爆速で求めれるやつ。
前処理をしておけば、$O(1)$ でクエリに答えることができる!! 強いっすね。
pythonには、`itertools.accumulate` という素晴らしいものがあります。
これを利用すると、累積和(一次元)が簡単に解くことができます。

以下のサンプルは、連続して並ぶK個の整数の和の最大値を求めるプログラムです。

```.py
from itertools import accumulate
 
N = 5 #要素数
K = 2 #何個要素が続く最大を求めるか
A = [3,4,-2, 8, 9]
 
B = [0] + A

B = list(accumulate(B)) #累積和
# B = [0, 3, 7, 5, 13, 22]
answer = []

for i in range(N-(K-1)):
    answer.append(B[i+K]-B[i])

print(max(answer))                     
```

#4. メモ探索

メモ化は、一度計算した値は記録しておきましょう。っていう考え方。
欲しい値が計算済みの場合はその値を使います。

何回も同じ値を使う場合などの便利です。

以下のプログラムはフィボナッチ数列のメモ化です。

```.py

MAX_N = 10
visited = [0]*(MAX_N+1) #訪れたかどうか flag
memo = [0]*(MAX_N+1) # 値の保持
n = 10 # 今回はフィボナッチの10項目の値を計算
memo[1] = 1

def fibonacci(n):
    if n == 0:
        return 0:
    elif n == 1:
        return 1
    elif visited[n] = True:
        return memo[n]
    else:
        visited[n] = True
        memo[n] = fibonacci(n-1) + fibonacci(n-2)

answer = fibonacci(n)

print(answer) 
```

#5. ナップサック問題


ナップサック問題とは、容量Cに、品物の価値が最大になるようにどう品物を選べば良いかの問題です。

<div align="center">
<img src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223559/44f9e401-125e-7b1a-dbd9-bb2ce06a08d8.png",height = 300, width=300>
</div>
(Wikipedia)


以下のプログラムは、V(価値)、W(重さ(容量))、W_max(最大容量)を表しています。


```.py

V = [4,5,2,8]
W = [2,2,1,3]
W_max = 5
N = 4

dp = [[0]*(W_max+1) for _ in range(N+1)]

for i in range(N):
    for j in range(W_max+1):
        if j < W[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-W[i]]+V[i])

print(dp[N][W_max])

```


#+α Python 二次元配列初期化速度

pythonで２次元配列を初期化するとき、下の２パターンではどっちが速いのか?

```speed.py
import time
N = 1000
 
start = time.clock()
a = [[0]*N for _ in range(N)]
end = time.clock()
print(end-start)
 
start1 = time.clock()
a = [ 0 for _ in range(N) for _ in range(N)]
end1 = time.clock()
print(end1-start1)
```

実行結果
0.007819
0.03606000000000001

明らかに *[[0]*N for _ in range(N)]*の方が速いようです