数字の配列内の最小合計を見つける

Question

私は、Excelのシート内の行数の連続する数字の最小合計を求めようとしています。 10.000行。

1 200 
2 -100 
3 -300 
4 100 
5 100 
6 100 

これは、-400行と2行（これはもちろん別の公式でもよい）を与えるはずです。

1 0 
2 100 
3 -100 
4 -100 
5 -100 
6 100 
7 -100 
8 100 

これは-300と3行などに

感謝を与える必要があります！このプロセス配列を使用

Answer 1

は10,000行に3-4秒かかりました。ここで

Sub minarr() 

Dim i&, j& 
Dim rngArr() As Variant 
Dim sum As Double 
Dim frstrw As Long 
Dim lstrw As Long 
Dim lastrow As Long 
Dim ws As Worksheet 
Dim Minout As Double 

Set ws = Sheets("Sheet28") 'Change to your sheet 

'Change column A to the column of your numbers in the next two lines. 
lastrow = ws.Range("A" & ws.Rows.Count).End(xlUp).row 
rngArr = ws.Range("A1:A" & lastrow).Value 

For i = 1 To lastrow 
    sum = rngArr(i, 1) 
    For j = i + 1 To lastrow 
     sum = sum + rngArr(j, 1) 
     If sum < Minout Then 
      Minout = sum 
      frstrw = i 
      lstrw = j 
     End If 
    Next j 
Next i 

Debug.Print Minout 
Debug.Print frstrw 
Debug.Print lstrw 

End Sub 

Answer 2

はデバッグO(n)ソリューションです。それは事実上瞬時に10,000項目です。

Function MinSum(Target As Range) As Variant 
    'Target is a 1-dimensional range of numbers 
    'Returns a variant array containing 
    '0) The minimum sum of consecutive numbers in R 
    '1) The starting index of the sum 
    '2) The ending index of the sum 

    Dim i As Long, n As Long 
    Dim A As Variant 'A(i,1) = value of best subsequence ending at i, A(i,2) is corresponding start value 
    Dim v As Variant 'currently scanned value 
    Dim minS As Variant 'the min sum 
    Dim minAt As Variant 'where it occurs in A 

    With Target 
     'initialize 
     n = .Cells.Count 
     ReDim A(1 To n, 1 To 2) 
     v = .Cells(1) 
     minS = v 
     minAt = 1 
     A(1, 1) = v 
     A(1, 2) = 1 

     'main loop 
     For i = 2 To n 
      v = .Cells(i) 
      'the best sequence ending at i extends previous one if previous one is negative: 
      If A(i - 1, 1) < 0 Then 
       A(i, 1) = A(i - 1, 1) + v 
       A(i, 2) = A(i - 1, 2) 'extend current subsequence 
      Else 'start new subsequence 
       A(i, 1) = v 
       A(i, 2) = i 
      End If 
      'see if we have a new min: 
      If A(i, 1) < minS Then 
       minS = A(i, 1) 
       minAt = i 
      End If 
     Next i 
    End With 

    MinSum = Array(minS, A(minAt, 2), minAt) 
End Function 

それは最小の和と2つのインデックスの両方を与える配列を返し、開始：アルゴリズムが（この問題に近い一致であると指摘している@のrajah9）maximum subarray problemを解決するためKadaneのアルゴリズムの変形であります配列内の合計の終わり。これは、配列数式として使用することができる：A10000、次いで、セルC1で：上のスクリーンショットで

、Iは、セルA1に=RANDBETWEEN(-100,100)を有するE1 Iは{=MinSum(A1:A10000)}（Ctrlキーを押しながらとして受け入れる入力+シフト有します配列式）。 10,000個の乱数の計算とminsumの決定の両方が0.5秒未満で完了します。