0

正数と負数を含む数値配列が与えられた場合、問題は、合計が最大で時間計算量が O(n) である連続したサブ配列を見つけることです。たとえば、[1,-2,3,10,-4 ,7,2,-5] は配列であり、サブ配列 [3, 10, -4, 7, 2] の最大合計は 18 です。では、O(n) 内でこのサブ配列を見つける方法は? どうも

4

3 に答える 3

2

このソリューションへのWikiリンク。これは、最大部分配列合計問題と呼ばれます。ソリューションは、O(n) 時間で実行される Kadane によって提供されます。

于 2013-07-17T13:33:09.677 に答える
0

アイデアは、累積シリーズを見て（値を何かの増分/減分として扱います）、次にこのシリーズの安値とそれに続く高値を見つけることです。

擬似コード:

sum = 0
low = Integer.MaxValue
highestSumSinceLow = Integer.MinValue
For i = 0 to Array.Length-1
  sum += Array[i]                            // keep track of cumulative value since start
  If sum < low Then                          
    low = sum                                // keep track of lowest sum since start so far
    substart = i + 1                         //    and set substart to next value
  sumsincelow = sum - low                    // calculate sum from that low to here
  If sumsincelow > highestSumSinceLow Then   
    highestSumSinceLow = sumsincelow         // keep track of highest sumsincelow
    subend = i                               //    and set subend to this value
Next i

配列全体を調べた後、合計が最大のサブ配列のインデックスをポイントします (これは ですsubstart) 。subendhighestSumSinceLow

これはおそらく最も単純で効率的なソリューションです。これは O(n) であり、一時配列を使用しません。開始から終了まで配列を 1 回通過するだけで、開始以降の累積合計の最小値と、それ以降の最大合計を追跡します。

于 2013-07-17T11:52:00.267 に答える
0

これがPythonでの解決策です。アイデアは、最大連続合計を検索することです。その合計が負の場合はリストを空にし、負でない場合はそれらの要素を保持する必要があります。

l =  [1,-2,3,10,-4,7,2,-5]

def find_max(l):
    s = 0 # Current sum
    lsum = [] # Current subarray
    res = (0, []) # Max value and subarray

    for v in l:
       s += v
       lsum.append(v)
       if s > res[0]:
         res = (s, lsum[:])
       elif s < 0:
         s = 0
         lsum = []

    return res

print find_max(l)

結果：

(18, [3, 10, -4, 7, 2])
于 2013-07-17T11:46:27.760 に答える