在数组中find最小的和

我正在试图find一个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

这是一个debugging的O(n)解决scheme。 这几乎是瞬间的10000个项目。 该algorithm是Kadanealgorithm求解最大子阵问题的一个变种（@ rajah9指出这个问题与这个问题是紧密匹配的）：

 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 

它返回一个数组，其中给出了最小总和和两个索引，数组中的总和的开始和结束。 它可以用作数组公式：

在上面的屏幕截图中，单元格A1：A10000中有=RANDBETWEEN(-100,100) ，然后在单元格C1：E1中有{=MinSum(A1:A10000)} （按Ctrl + Shift + Enter接受数组公式）。 10,000个随机数的计算和判决都不到半秒。