[VBS][算法实战006]分治法解“最大子列和问题”

老刘发表于 2019-10-30 17:58

本帖最后由老刘于 2019-10-30 18:03 编辑

数学符号语言描述：

文字描述：
最大子数列问题的目标是在数列的一维方向找到一个连续的子数列，使该子数列的和最大。例如，对一个数列 -2, 1, -3, 4, -1, 2, 1, -5, 4，其连续子数列中和最大的是 4, -1, 2, 1, 其和为6。
若最大子列和为负，则结果取0。
以下解法非最优（时间复杂度O(nlogn)，已有O(n)的算法），仅为分治思想练习：

Option Explicit
Dim Arr

Arr = Array(4,-3,5,-2,-1,2,6,-2) '为11
WScript.Echo Max(MaxSubseqSum(1,1,UBound(Arr) + 1),0)

Arr = Array(-2,1,-3,4,-1,2,1,-5,4) '为6
WScript.Echo Max(MaxSubseqSum(1,1,UBound(Arr) + 1),0)

Arr = Array(-2,11,-4,13,-5,-2) '为20
WScript.Echo Max(MaxSubseqSum(1,1,UBound(Arr) + 1),0)

Arr = Array(-2,6,-1,5,4,-7,2,3) '为14
WScript.Echo Max(MaxSubseqSum(1,1,UBound(Arr) + 1),0)

Function MaxSubseqSum(ByVal ptrListStart,ByVal ptrListMiddle,ByVal ptrListEnd)
   Dim numMaxLeft,numMaxRight,numMaxUnion

   Rem 求左半段最大子列和。
   If ptrListStart = ptrListMiddle Then '只有一个元素
            numMaxLeft = GetItem(Arr,ptrListStart)
   Else
            If (ptrListMiddle - ptrListStart + 1) Mod 2 = 0 Then '有偶数个元素，平均分配
                     numMaxLeft = MaxSubseqSum(ptrListStart,(ptrListStart + ptrListMiddle - 1)\2,ptrListMiddle)
            Else '有奇数个元素，左半段分配一个，右半段分配剩下的
                     numMaxLeft = MaxSubseqSum(ptrListStart,ptrListStart,ptrListMiddle)
            End If
   End If

   Rem 求右半段最大子列和。
   If ptrListEnd - ptrListMiddle = 1 Then '只有一个元素
            numMaxRight= GetItem(Arr,ptrListEnd)
   Else
            If (ptrListEnd - ptrListMiddle) Mod 2 = 0 Then '偶数个元素
                     numMaxRight = MaxSubseqSum(ptrListMiddle + 1,(ptrListMiddle + ptrListEnd)\2,ptrListEnd)
            Else
                     numMaxRight = MaxSubseqSum(ptrListMiddle + 1,ptrListMiddle + 1,ptrListEnd)
            End If
   End If

   Rem 求左右合并最大子列和。
   Rem 左半边。
   Dim ptrNow,numUnionNow,numMaxUnionLeft,numMaxUnionRight
   numUnionNow = 0
   numMaxUnionLeft = 0
   For ptrNow = ptrListMiddle To ptrListStart Step -1
            numUnionNow = numUnionNow + GetItem(Arr,ptrNow)
            numMaxUnionLeft = Max(numMaxUnionLeft,numUnionNow)
   Next
   Rem 右半边。
   numUnionNow = 0
   numMaxUnionRight = 0
   For ptrNow = ptrListMiddle + 1 To ptrListEnd
            numUnionNow = numUnionNow + GetItem(Arr,ptrNow)
            numMaxUnionRight = Max(numMaxUnionRight,numUnionNow)
   Next
   Rem 求合并。
   numMaxUnion = numMaxUnionLeft + numMaxUnionRight

   Rem 左半段、右半段、左右合并取最大。
   MaxSubseqSum = Max(Max(numMaxLeft,numMaxRight),numMaxUnion)
End Function

Function GetItem(ByVal Arr,ByVal Ptr) '手动构造从1开始的数组
   GetItem = Arr(Ptr - 1)
End Function

Function Max(ByVal Num1,ByVal Num2)
   If Num1 > Num2 Then
            Max = Num1
   Else
            Max = Num2
   End If
End Function

pumishuo 发表于 2019-11-12 00:18

vbs可以的

页: [1]

吾爱破解 - 52pojie.cn's Archiver

[VBS][算法实战006]分治法解“最大子列和问题”