365 体育在线网址_365bet体育线上平台_谁有365体育在线网址新手入门导读[视频教程]365 体育在线网址_365bet体育线上平台_谁有365体育在线网址基础视频教程[视频教程]VBS基础视频教程
[365 体育在线网址_365bet体育线上平台_谁有365体育在线网址文件精品]365 体育在线网址_365bet体育线上平台_谁有365体育在线网址版照片整理器[365 体育在线网址_365bet体育线上平台_谁有365体育在线网址文件精品]纯365 体育在线网址_365bet体育线上平台_谁有365体育在线网址备份&还原驱动在线第三方下载
返回列表 发帖

不限语言解决“最大子列和问题”

本帖最后由 老刘1号 于 2019-10-30 09:35 编辑
数学符号语言描述:

文字描述:
最大子数列问题的目标是在数列的一维方向找到一个连续的子数列,使该子数列的和最大。例如,对一个数列 −2, 1, −3, 4, −1, 2, 1, −5, 4,其连续子数列中和最大的是 4, −1, 2, 1, 其和为6。
若最大子列和为负,则结果取0。

相关链接:百度百科

附一个分治法的(非最优解法,仅作分治思想练习)
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)

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(Arr,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
附件: 您需要登录才可以下载或查看附件。没有帐号?注册

凑个数
  1. Function Get-MaxSum([double[]]$int) {
  2. $tmp = 0;
  3. if ($int.Count -eq 1) {
  4. if ($int[0] -lt 0) { return 0 }else { return $int[0] }
  5. }
  6. for ($i = 0; $i -lt $int.Count - 1; $i++) {
  7. $sum = $int[$i];
  8. for ($j = $i + 1; $j -lt $int.Count; $j++) {
  9. $sum += $int[$j];
  10. if ($sum -ge $tmp) { $tmp = $sum }
  11. }
  12. }
  13. return $tmp;
  14. }
  15. Get-MaxSum 4, -3, 5, -2, -1, 2, 6, -2
  16. Get-MaxSum -2,1,-3,4,-1,2,1,-5,4
复制代码
========说实话 都没弄清题意 ===========
1

评分人数

    • 老刘1号: 双循环,时间复杂度O(n2),简单直观技术 + 1
QQ: 458609586

TOP

返回列表