再帰と動的計画法のアルゴリズムに関するプログラムのエラー

前提・実現したいこと

関数呼び出しをするプログラムの時間計算量についてで明記したプログラムを、動的計画法で書こうとしています。
目的としては、時間計算量がO(n^2)(予測）から動的計画法でO(n)に改善するためです。

関数呼び出しをするプログラムのcountonesにおいて以下の再帰関係があると考えられます。

def countones(A,i)の再帰関係
・countones(A,i) = 1 if i = len(A) and A[i] = 1
・countones(A,i) = countones(A,i) if i<len(A) and A[i] = 1
・countones(A,i) = 0 if A[i] = 0

発生している問題・エラーメッセージ

前提条件の考え方に問題がある可能性もありますが、現在のプログラムでは以下のエラーが出ている状態で、どのように修正していくべきか悩んでいます。

Traceback (most recent call last):
  File "longestones2.py", line 21, in <module>
    print(longestnum2(A))
  File "longestones2.py", line 6, in longestnum2
    if A[i] == 0:
IndexError: list index out of range

該当のソースコード

python
1def longestnum2(A):
2	max = 0
3	T = [0] * len(A)
4	for j in range(len(A)): #繰り返し　O(n)
5		i = len(A) - j
6		if A[i] == 0:
7			T[i] = 0
8		elif i == len(A) and A[i] == 1:
9			T[i] = 1
10		else:
11		 	T[i] = T[i+1] + 1
12		if max < T[i]:
13			max = T[i]
14
15	return max
16
17
18
19
20A = [1,1,0,0,0,1,1,1,1,0,0]
21print(longestnum2(A))

補足情報（FW/ツールのバージョンなど）

python 3.6

行動規範の内容に同意します

回答2件

ベストアンサー

Python
1#def longestnum2(A):
2def longestnum2(A : list) -> int:
3    max = 0
4    #T = [0] * len(A)
5    T = copy.deepcopy(A)
6    for j in range(len(A)): #繰り返し　O(n)
7        #i = len(A) - j
8        i = (len(A) - 1) - j
9        if A[i] == 0:
10            T[i] = 0
11        #elif i == len(A) and A[i] == 1:
12        elif i == len(A) - 1 and A[i] == 1:
13             T[i] = 1
14        else:
15             #ここ何がしたいのか分かりません。
16             T[i] = T[i+1] + 1
17        #ここも何がしたいのか分かりません。
18        if max < T[i]:
19            max = T[i]
20
21    return max