この質問が何を尋ねようとしているのか分からなくなってきました。
整数のリストを入力として受け取る関数 (最小合計サブリスト) を記述
mssl()します。次に、入力リストの最大合計サブリストの合計を計算して返します。最大合計サブリストは、エントリの合計が最大となる入力リストのサブリスト (スライス) です。空のサブリストは、合計が 0 であると定義されます。たとえば、リストの最大合計サブリスト[4, -2, -8, 5, -2, 7, 7, 2, -6, 5]は で[5, -2, 7, 7, 2]、そのエントリの合計は です19。
この関数を使用すると、次のような結果が返されるはずです。
>>> l = [4, -2, -8, 5, -2, 7, 7, 2, -6, 5]
>>> mssl(l)
19
>>> mssl([3,4,5])
12
>>> mssl([-2,-3,-5])
0
どうすればいいですか？
これが私の現在の試みですが、期待した結果は得られません。
def mssl(x):
' list ==> int '
res = 0
for a in x:
if a >= 0:
res = sum(x)
return res
else:
return 0
ベストアンサー1
実は、非常にエレガントで効率的な解決策があります。動的プログラミング。 かかるO(1)空間、 そして時間通りに-- これに勝るものはありません!
Aを入力配列（ゼロインデックス）として定義し、を位置 で終了するが位置 を含まないすべてのサブリスト（つまり、すべてのサブリスト）B[i]の最大合計として定義します。したがって、 、および、、などとなります。すると、明らかに、解は によって単純に与えられます。iA[j:i]B[0] = 0B[1] = max(B[0]+A[0], 0)B[2] = max(B[1]+A[1], 0)B[3] = max(B[2]+A[2], 0)max(B[0], ..., B[n])
Bすべての値は前の値のみに依存するためB、配列全体を保存する必要がなくなりB、O(1) のスペースが保証されます。
このアプローチにより、mssl非常に単純なループに短縮されます。
def mssl(l):
best = cur = 0
for i in l:
cur = max(cur + i, 0)
best = max(best, cur)
return best
デモンストレーション：
>>> mssl([3,4,5])
12
>>> mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5])
19
>>> mssl([-2,-3,-5])
0
開始スライス インデックスと終了スライス インデックスも必要な場合は、さらにいくつかの情報を追跡する必要があります (これは依然として O(1) のスペースと O(n) の時間を要することに注意してください。少し複雑になります)。
def mssl(l):
best = cur = 0
curi = starti = besti = 0
for ind, i in enumerate(l):
if cur+i > 0:
cur += i
else: # reset start position
cur, curi = 0, ind+1
if cur > best:
starti, besti, best = curi, ind+1, cur
return starti, besti, best
これは、かつが最大と(a, b, c)なるタプルを返します。sum(l[a:b]) == cc
>>> mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5])
(3, 8, 19)
>>> sum([4, -2, -8, 5, -2, 7, 7, 2, -6, 5][3:8])
19