-
単純な方法
def rangeSum(x, i, j): # 配列 x の i 番目から j 番目までの和
s = 0
for k in range(i, j + 1):
s = s + x[k]
return s
def maxSumRange(x): # 配列 x の部分要素和の最大値
m = 0 # 最大値の候補
for i in range(0, len(x)):
for j in range(i, len(x)):
m = max(m, rangeSum(x, i, j))
return m
-
漸化式を再帰プログラムに
def ms(x, k): # 漸化式をそのまま再帰にしたもの
if k == 0:
return x[0]
else:
return max(x[k], ms(x, k - 1) + x[k])
def maxSumRange(x): # 配列 x の部分要素和の最大値
m = 0
for i in range(0, len(x)):
m = max(m, ms(x, i))
return m
-
動的計画法を使ったプログラム
def maxSumRange(x):
m = 0
ms = ita.array.make1d(len(x)) # 表を用意
for i in range(0, len(x)):
ms[i] = ms_core(ms, x, i) # 表を埋める
m = max(m, ms[i])
return m
def ms_core(ms, x, k):
if k == 0:
return x[0]
else:
return max(x[k], ms[k - 1] + x[k])def maxSumRange(x):
-
lcs の再帰プログラム
def commonDNA(x, y):
return lcs(x, y, len(x), len(y))
def lcs(x, y, i, j):
if i == 0 or j == 0:
return 0
else:
r = max(lcs(x, y, i - 1, j), lcs(x, y, i, j - 1)) # いずれにせよ考慮するケース
if x[i - 1] == y[j - 1]:
r = max(r, 1 + lcs(x, y, i - 1, j - 1)) # x[i - 1] == y[j - 1] なら考慮するケース
return r
-
lcs の動的計画法
def commonDNA(x,y):
n = len(x)
m = len(y)
lcs = ita.array.make2d(n+1,m+1)
for i in range(0, n + 1):
for j in range(0, m + 1): # 「短い」場合から順に
lcs[i][j] = fill(lcs, x, y, i, j) # fill(lcs, x, y, i , j) = lcs(i, j)
return lcs[n][m]
def fill(lcs, x, y, i, j):
if i == 0 or j == 0:
return 0
else:
r = max(lcs[i - 1][j], lcs[i][j - 1]) # いずれにせよ考慮するケース
if x[i-1] == y[j-1]:
r = max(r, 1 + lcs[i - 1][j - 1]) # x[i - 1] == y[j - 1] なら考慮するケース
return r