Maximum Sum Sublistというプログラミング問題をO(n^2)とO(n^3)で解くアルゴリズムのちがいについて
Maximum Sum Sublistという
配列で複数の整数が与えられた時に、和が最も大きくなる範囲とその和を求める
プログラミング問題があります。
この問題は時間計算量O(n^2)とO(n^3)で解くアルゴリズムがあるのですが
同じアルゴリズムでも解釈によってO(n^2)にもO(n^3)にもなるとのことで
明確にO(n^2)とO(n^3)と区別できるプログラムもしくはアルゴリズムをそれぞれ探しています。
以下のコードは時間計算量O(n^2)と考えていますが、A[i:j+1]がO(j − i)回かかるので、O(n^3)と他の回答で説明されました。
def solution(A):
start = None
end = None
max_total = 0
for i in range(len(A)):
for j in range(i, len(A)):
tmp = sum(A[i:j+1])
if max_total < tmp:
max_total = tmp
start = i
end = j
return max_total, start, end
if __name__ == '__main__':
A = [18, -10, 30, 23, -26]
ans = solution(A)
print(ans)
Maximum Sum Sublistを解く時に
明確にO(n^2)とO(n^3)と区別できるプログラムもしくはアルゴリズムが知りたいです。