批处理之家 - Powered by Discuz! Board

标题: 不限语言解决“最大子列和问题” [打印本页]

作者: 老刘1号 时间: 2019-10-30 09:33 标题: 不限语言解决“最大子列和问题”

数学符号语言描述：

文字描述：
最大子数列问题的目标是在数列的一维方向找到一个连续的子数列，使该子数列的和最大。例如，对一个数列 −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)

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

作者: xczxczxcz 时间: 2019-10-30 13:05

凑个数

Function Get-MaxSum([double[]]$int) {
	$tmp = 0;
	if ($int.Count -eq 1) {
		if ($int[0] -lt 0) { return 0 }else { return $int[0] }
	}
	for ($i = 0; $i -lt $int.Count - 1; $i++) {
		$sum = $int[$i];
		for ($j = $i + 1; $j -lt $int.Count; $j++) {
			$sum += $int[$j];
			if ($sum -ge $tmp) { $tmp = $sum }
		}
	}
	return $tmp;
}
Get-MaxSum 4, -3, 5, -2, -1, 2, 6, -2
Get-MaxSum -2,1,-3,4,-1,2,1,-5,4
复制代码

========说实话都没弄清题意 ===========

作者: bailong360 时间: 2019-10-30 18:08

记得以前做过这道题

pub fn find_max_squence(v: &[i32]) -> i32 {
    let mut max_sum = 0;
    let mut tmp_sum = 0;
    for i in v {
        tmp_sum = (tmp_sum + i).max(0);
        max_sum = max_sum.max(tmp_sum);
    }
    max_sum
}
复制代码

在线体验: https://play.rust-lang.org/?vers ... f4a9e2439dca3ea1117

作者: bailong360 时间: 2019-10-30 21:58

pub fn find_max_squence(v: &[i32]) -> i32 {
let mut max_sum = 0;
let mut tmp_sum = 0;
for i in v {
tmp_sum = (tmp_sum + i).max(0);
max_sum = max_sum.max(tmp_sum);
}
max_sum
}

我也来试试代码高亮
话说 Windows 上能识别 monospace 字体么? (上面代码是不是等宽的

作者: 老刘1号 时间: 2019-10-30 22:10

回复 4# bailong360

显示的是等宽的233

作者: WHY 时间: 2019-10-30 22:14

以前我也碰到过，印象中是这样？

@echo off & setlocal enabledelayedexpansion
set /a min=0, result=0
for %%i in (-2, 1, -3, 4, -1, 2, 1, -5, 4) do (
    set /a sum+=%%i, tmpSum=sum-min
    if !result! LSS !tmpSum! set "result=!tmpSum!"
    if !min! GTR !sum! set "min=!sum!"
)
if !result! LSS 0 set "result=0"
echo;!result!
pause
复制代码

欢迎光临批处理之家 (http://bbs.bathome.net/)