python - 最大合計サブリスト?

Question

この質問が何を尋ねようとしているのか、私は混乱しています。

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

score 55 · Accepted Answer

実際には、動的計画法を使用した非常に洗練された非常に効率的なソリューションがあります。O(1) のスペースとO(n) の時間がかかります。これに勝るものはありません。

A入力配列 (ゼロインデックス) となるように定義しB[i]、位置で終わるが位置を含まないiすべてのサブリスト (つまり、すべてのサブリストA[j:i]) の最大合計となるように定義します。したがって、、、、、、B[0] = 0などB[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全体を格納することを避けることができ、O(1) スペースが保証されます。B

このアプローチで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

score 7 · Accepted Answer

これはサブアレイの最大の問題です。Kadaneのアルゴリズムは、O(n)時間とO(1)空間でそれを解決でき、次のようになります。

def mssl(x):
    max_ending_here = max_so_far = 0
    for a in x:
        max_ending_here = max(0, max_ending_here + a)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

score 3 · Accepted Answer

したがって、サブリスト（または同じものと見なすことができるスライス）が何であるかを理解している場合、スライスは開始インデックスと終了インデックスによって定義されます。

したがって、考えられるすべての開始インデックスと終了インデックスを繰り返し処理し、対応する合計を計算してから、最大値を返すことができます。

ヒント：開始インデックスは0からまで変化しますlen(given_list)-1。終了インデックスはfromからstart_indexまでlen(given_list)-1です。ネストされたforループを使用して、考えられるすべての組み合わせを確認できます。

score 2 · Accepted Answer

簡単な解決策は、リストを繰り返し処理し、最適なスライスが見つかるまでスライスを追加してみることです。ここには、実際のサブリストを返すオプションも含まれています。デフォルトでは、これはFalseです。ルックアップよりも単純なので、この目的でdefaultdictを使用しました。

from collections import defaultdict

def mssl(lst, return_sublist=False):
    d = defaultdict(list)
    for i in range(len(lst)+1):
        for j in range(len(lst)+1):
            d[sum(lst[i:j])].append(lst[i:j])
    key = max(d.keys())
    if return_sublist:
        return (key, d[key])
    return key

print mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5])
19
print mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5], True)
(19, [[5, -2, 7, 7, 2]])

ボーナス：リスト内包法：

def _mssl(lst):
    return max( sum( lst[i:j] ) for i in xrange(len(lst)+1) for j in xrange(i, len(lst)+1) )

score 1 · Accepted Answer

小さいサブセクションの合計が最大になるように、リストの小さいサブセクションを選択するように求められます。

リストがすべて正の[1 2 3]場合、もちろん、合計が最大のサブセクションは、リスト全体の合計である[1 2 3]6にすぎません。

リストがすべて負の場合、[-1 -2 -3]合計が最大のサブセクションは、合計が[]0のサブセクションではありません。

ただし、リストに肯定的なものと否定的なものがある場合、決定はより困難になります

[1 2 3 -100 3 4 5][3 4 5]表示して12を返す必要があります

[1 2 3 -2 3 4 5]すべてを使用して16を返す必要があります

score 1 · Accepted Answer

これは、最大の合計を生成する配列内のサブシーケンスを見つけるための問題であると想定しています。最大合計 SUBSET 問題を検索しているときに、この問題に遭遇しました。

この質問の Java 実装:

public static int maximumSumSubSequence(int[] array) {

    if (null == array) {
        return -1;
    }

    int maxSum = Integer.MIN_VALUE;
    int startIndexFinal = 0;
    int endIndexFinal = 0;
    int currentSum = 0;
    int startIndexCurrent = 0;

    for (int i = 0; i < array.length; i++) {
        currentSum += array[i];

        if (currentSum > maxSum) {
            maxSum = currentSum;
            endIndexFinal = i;
            startIndexFinal = startIndexCurrent;
        }
        if (currentSum <= 0) {
            currentSum = 0;
            startIndexCurrent = i + 1;
        }
    }
    System.out.println("startIndex: " + startIndexFinal + " endIndex: " + endIndexFinal);
    return maxSum;
}

score 0 · Accepted Answer

この区別は、問題を解決する方法を理解しようとしているように見えるOPにとってはおそらく重要ではありませんが、言及する価値があると思いました。

ここでの他の解決策は、リストのすべてのサブパートを繰り返し合計することを含みます。もちろん、からの合計がすでにわかっている場合は、からの合計を取得するためにそれらを再度加算する必要がないため、動的計画法を使用してこれらの繰り返しの合計をi回避jできiますj+1。

つまり、部分和の2次元配列を作成して、partsum[i, j] == sum(lst[i:j])。次のようなものです（インデックス作成が簡単なため辞書を使用します。numpy配列も同様に簡単で効率的です）：

import operator

def mssl(lst, return_sublist=False):
    partsum = { (0, 0): 0 }  # to correctly get empty list if all are negative
    for i in xrange(len(lst) - 1):  # or range() in python 3
        last = partsum[i, i+1] = lst[i]
        for j in xrange(i+1, len(lst)):
            last = partsum[i, j+1] = last + lst[j]

    if return_sublist:
        (i, j), sum = max(partsum.iteritems(), key=operator.itemgetter(1))
        return sum, lst[i:j]

    return max(partsum.itervalues())  # or viewvalues() in 2.7 / values() in 3.x

これには、Lev / InbarのアプローチのO（n ^ 3）時間とO（1）メモリとは対照的に、O（n ^ 2）時間とメモリが必要です（Inbarの最初のコード例のように愚かに実装されていない場合）。

score 0 · Accepted Answer

誰かがコードの長いバージョンを探しているなら、ここにあります:

def mesl(lst):
    sub_sum = list()
    row_sum = list()
    for i in range(len(lst)):
        sub_sum = list()
        sub_sum.append(lst[i])
        k = 1
        for j in range(i+1,len(lst)):
            sub_sum.append(sub_sum[k-1] + lst[j])
            k+=1
        row_sum.append(max(sub_sum))      
    sum = max(row_sum)
    if  sum < 0:
        sum = 0
    return sum

score 0 · Accepted Answer

最大部分配列の問題に対する JavaScript の最短かつ最良の解決策は次のとおりです。

var maxSubArray = function(nums) {
    for (let i = 1; i < nums.length; i++){
        nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
    }
    return Math.max(...nums);
};

python - 最大合計サブリスト?

13 に答える 13

Related

Reference