Поиск минимальной суммы в массиве чисел

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

Использование Массивы этот процесс занимает 3-4 секунды на 10000 строк:

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 предметов. Алгоритм представляет собой вариант алгоритма Kadane для решения maximum subarray problem (который @ 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 

Он возвращает массив, который дает как минимальную сумму и два индекса, начало и конец суммы в массиве. Он может быть использован в качестве формулы массива:

В приведенном выше скриншоте, у меня =RANDBETWEEN(-100,100) в ячейках A1: A10000, а затем в ячейках С1: Е1 меня {=MinSum(A1:A10000)} (Ctrl + Shift + Enter, чтобы принять в качестве формула массива). И вычисление 10 000 случайных чисел, и определение минимальной суммы занимают менее половины секунды.