不限语言解决“最大子列和问题”
[i=s] 本帖最后由 老刘1号 于 2019-10-30 18:08 编辑 [/i][quote][size=5]数学符号语言描述:
[attach]12215[/attach]
文字描述:
最大子数列问题的目标是在数列的一维方向找到一个连续的子数列,使该子数列的和最大。例如,对一个数列 −2, 1, −3, 4, −1, 2, 1, −5, 4,其连续子数列中和最大的是 4, −1, 2, 1, 其和为6。
若最大子列和为负,则结果取0。[/quote]
相关链接:[url=https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%AD%90%E6%95%B0%E5%88%97%E9%97%AE%E9%A2%98/22828059?fr=aladdin]百度百科[/url]
附一个分治法的(非最优解法,时间复杂度O(nlogn),已有O(n)的算法;仅作分治思想练习)[/size]
[color=DeepSkyBlue]Option[/color] [color=DeepSkyBlue]Explicit[/color]
[color=DeepSkyBlue]Dim[/color] Arr
Arr [color=DarkOrange]=[/color] [color=Red]Array[/color][color=DarkOrange]([/color]4[color=DarkOrange],[/color][color=DarkOrange]-[/color]3[color=DarkOrange],[/color]5[color=DarkOrange],[/color][color=DarkOrange]-[/color]2[color=DarkOrange],[/color][color=DarkOrange]-[/color]1[color=DarkOrange],[/color]2[color=DarkOrange],[/color]6[color=DarkOrange],[/color][color=DarkOrange]-[/color]2[color=DarkOrange])[/color] [color=Green]'为11[/color]
[color=Blue]WScript[/color][color=DarkOrange].[/color]Echo Max[color=DarkOrange]([/color]MaxSubseqSum[color=DarkOrange]([/color]1[color=DarkOrange],[/color]1[color=DarkOrange],[/color][color=Red]UBound[/color][color=DarkOrange]([/color]Arr[color=DarkOrange])[/color] [color=DarkOrange]+[/color] 1[color=DarkOrange])[/color][color=DarkOrange],[/color]0[color=DarkOrange])[/color]
Arr [color=DarkOrange]=[/color] [color=Red]Array[/color][color=DarkOrange]([/color][color=DarkOrange]-[/color]2[color=DarkOrange],[/color]1[color=DarkOrange],[/color][color=DarkOrange]-[/color]3[color=DarkOrange],[/color]4[color=DarkOrange],[/color][color=DarkOrange]-[/color]1[color=DarkOrange],[/color]2[color=DarkOrange],[/color]1[color=DarkOrange],[/color][color=DarkOrange]-[/color]5[color=DarkOrange],[/color]4[color=DarkOrange])[/color] [color=Green]'为6[/color]
[color=Blue]WScript[/color][color=DarkOrange].[/color]Echo Max[color=DarkOrange]([/color]MaxSubseqSum[color=DarkOrange]([/color]1[color=DarkOrange],[/color]1[color=DarkOrange],[/color][color=Red]UBound[/color][color=DarkOrange]([/color]Arr[color=DarkOrange])[/color] [color=DarkOrange]+[/color] 1[color=DarkOrange])[/color][color=DarkOrange],[/color]0[color=DarkOrange])[/color]
[color=DeepSkyBlue]Function[/color] MaxSubseqSum[color=DarkOrange]([/color][color=DeepSkyBlue]ByVal[/color] ptrListStart[color=DarkOrange],[/color][color=DeepSkyBlue]ByVal[/color] ptrListMiddle[color=DarkOrange],[/color][color=DeepSkyBlue]ByVal[/color] ptrListEnd[color=DarkOrange])[/color]
[color=DeepSkyBlue]Dim[/color] numMaxLeft[color=DarkOrange],[/color]numMaxRight[color=DarkOrange],[/color]numMaxUnion
[color=Green] Rem 求左半段最大子列和。[/color]
[color=DeepSkyBlue]If[/color] ptrListStart [color=DarkOrange]=[/color] ptrListMiddle [color=DeepSkyBlue]Then[/color] [color=Green]'只有一个元素[/color]
numMaxLeft [color=DarkOrange]=[/color] GetItem[color=DarkOrange]([/color]Arr[color=DarkOrange],[/color]ptrListStart[color=DarkOrange])[/color]
[color=DeepSkyBlue]Else[/color]
[color=DeepSkyBlue]If[/color] [color=DarkOrange]([/color]ptrListMiddle [color=DarkOrange]-[/color] ptrListStart [color=DarkOrange]+[/color] 1[color=DarkOrange])[/color] [color=DeepSkyBlue]Mod[/color] 2 [color=DarkOrange]=[/color] 0 [color=DeepSkyBlue]Then[/color] [color=Green]'有偶数个元素,平均分配[/color]
numMaxLeft [color=DarkOrange]=[/color] MaxSubseqSum[color=DarkOrange]([/color]ptrListStart[color=DarkOrange],[/color][color=DarkOrange]([/color]ptrListStart [color=DarkOrange]+[/color] ptrListMiddle [color=DarkOrange]-[/color] 1[color=DarkOrange])[/color][color=DarkOrange]\[/color]2[color=DarkOrange],[/color]ptrListMiddle[color=DarkOrange])[/color]
[color=DeepSkyBlue]Else[/color] [color=Green]'有奇数个元素,左半段分配一个,右半段分配剩下的[/color]
numMaxLeft [color=DarkOrange]=[/color] MaxSubseqSum[color=DarkOrange]([/color]ptrListStart[color=DarkOrange],[/color]ptrListStart[color=DarkOrange],[/color]ptrListMiddle[color=DarkOrange])[/color]
[color=DeepSkyBlue]End[/color] [color=DeepSkyBlue]If[/color]
[color=DeepSkyBlue]End[/color] [color=DeepSkyBlue]If[/color]
[color=Green] Rem 求右半段最大子列和。[/color]
[color=DeepSkyBlue]If[/color] ptrListEnd [color=DarkOrange]-[/color] ptrListMiddle [color=DarkOrange]=[/color] 1 [color=DeepSkyBlue]Then[/color] [color=Green]'只有一个元素[/color]
numMaxRight [color=DarkOrange]=[/color] GetItem[color=DarkOrange]([/color]Arr[color=DarkOrange],[/color]ptrListEnd[color=DarkOrange])[/color]
[color=DeepSkyBlue]Else[/color]
[color=DeepSkyBlue]If[/color] [color=DarkOrange]([/color]ptrListEnd [color=DarkOrange]-[/color] ptrListMiddle[color=DarkOrange])[/color] [color=DeepSkyBlue]Mod[/color] 2 [color=DarkOrange]=[/color] 0 [color=DeepSkyBlue]Then[/color] [color=Green]'偶数个元素[/color]
numMaxRight [color=DarkOrange]=[/color] MaxSubseqSum[color=DarkOrange]([/color]ptrListMiddle [color=DarkOrange]+[/color] 1[color=DarkOrange],[/color][color=DarkOrange]([/color]ptrListMiddle [color=DarkOrange]+[/color] ptrListEnd[color=DarkOrange])[/color][color=DarkOrange]\[/color]2[color=DarkOrange],[/color]ptrListEnd[color=DarkOrange])[/color]
[color=DeepSkyBlue]Else[/color]
numMaxRight [color=DarkOrange]=[/color] MaxSubseqSum[color=DarkOrange]([/color]ptrListMiddle [color=DarkOrange]+[/color] 1[color=DarkOrange],[/color]ptrListMiddle [color=DarkOrange]+[/color] 1[color=DarkOrange],[/color]ptrListEnd[color=DarkOrange])[/color]
[color=DeepSkyBlue]End[/color] [color=DeepSkyBlue]If[/color]
[color=DeepSkyBlue]End[/color] [color=DeepSkyBlue]If[/color]
[color=Green] Rem 求左右合并最大子列和。[/color]
[color=Green] Rem 左半边。[/color]
[color=DeepSkyBlue]Dim[/color] ptrNow[color=DarkOrange],[/color]numUnionNow[color=DarkOrange],[/color]numMaxUnionLeft[color=DarkOrange],[/color]numMaxUnionRight
numUnionNow [color=DarkOrange]=[/color] 0
numMaxUnionLeft [color=DarkOrange]=[/color] 0
[color=DeepSkyBlue]For[/color] ptrNow [color=DarkOrange]=[/color] ptrListMiddle [color=DeepSkyBlue]To[/color] ptrListStart Step [color=DarkOrange]-[/color]1
numUnionNow [color=DarkOrange]=[/color] numUnionNow [color=DarkOrange]+[/color] GetItem[color=DarkOrange]([/color]Arr[color=DarkOrange],[/color]ptrNow[color=DarkOrange])[/color]
numMaxUnionLeft [color=DarkOrange]=[/color] Max[color=DarkOrange]([/color]numMaxUnionLeft[color=DarkOrange],[/color]numUnionNow[color=DarkOrange])[/color]
[color=DeepSkyBlue]Next[/color]
[color=Green] Rem 右半边。[/color]
numUnionNow [color=DarkOrange]=[/color] 0
numMaxUnionRight [color=DarkOrange]=[/color] 0
[color=DeepSkyBlue]For[/color] ptrNow [color=DarkOrange]=[/color] ptrListMiddle [color=DarkOrange]+[/color] 1 [color=DeepSkyBlue]To[/color] ptrListEnd
numUnionNow [color=DarkOrange]=[/color] numUnionNow [color=DarkOrange]+[/color] GetItem[color=DarkOrange]([/color]Arr[color=DarkOrange],[/color]ptrNow[color=DarkOrange])[/color]
numMaxUnionRight [color=DarkOrange]=[/color] Max[color=DarkOrange]([/color]numMaxUnionRight[color=DarkOrange],[/color]numUnionNow[color=DarkOrange])[/color]
[color=DeepSkyBlue]Next[/color]
[color=Green] Rem 求合并。[/color]
numMaxUnion [color=DarkOrange]=[/color] numMaxUnionLeft [color=DarkOrange]+[/color] numMaxUnionRight
[color=Green] Rem 左半段、右半段、左右合并取最大。[/color]
MaxSubseqSum [color=DarkOrange]=[/color] Max[color=DarkOrange]([/color]Max[color=DarkOrange]([/color]numMaxLeft[color=DarkOrange],[/color]numMaxRight[color=DarkOrange])[/color][color=DarkOrange],[/color]numMaxUnion[color=DarkOrange])[/color]
[color=DeepSkyBlue]End[/color] [color=DeepSkyBlue]Function[/color]
[color=DeepSkyBlue]Function[/color] GetItem[color=DarkOrange]([/color]Arr[color=DarkOrange],[/color]Ptr[color=DarkOrange])[/color] [color=Green]'手动构造从1开始的数组[/color]
GetItem [color=DarkOrange]=[/color] Arr[color=DarkOrange]([/color]Ptr [color=DarkOrange]-[/color] 1[color=DarkOrange])[/color]
[color=DeepSkyBlue]End[/color] [color=DeepSkyBlue]Function[/color]
[color=DeepSkyBlue]Function[/color] Max[color=DarkOrange]([/color][color=DeepSkyBlue]ByVal[/color] Num1[color=DarkOrange],[/color][color=DeepSkyBlue]ByVal[/color] Num2[color=DarkOrange])[/color]
[color=DeepSkyBlue]If[/color] Num1 [color=DarkOrange]>[/color] Num2 [color=DeepSkyBlue]Then[/color]
Max [color=DarkOrange]=[/color] Num1
[color=DeepSkyBlue]Else[/color]
Max [color=DarkOrange]=[/color] Num2
[color=DeepSkyBlue]End[/color] [color=DeepSkyBlue]If[/color]
[color=DeepSkyBlue]End[/color] [color=DeepSkyBlue]Function[/color] 凑个数[code]
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
[/code]========说实话 都没弄清题意 =========== 记得以前做过这道题[code]
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
}
[/code]在线体验: [url]https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0332cfb81c11ef4a9e2439dca3ea1117[/url] [table=98%,#282a36]
[tr][td][font=monospace][color=#ff79c6]pub[/color][color=#f8f8f2] [/color][color=#8be9fd]fn[/color][color=#f8f8f2] [/color][color=#50fa7b]find_max_squence[/color][color=#f8f8f2]([/color][color=#ffb86c]v[/color][color=#f8f8f2]:[/color][color=#f8f8f2] [/color][color=#ff79c6]&[/color][color=#f8f8f2][[/color][color=#8be9fd]i32[/color][color=#f8f8f2]][/color][color=#f8f8f2])[/color][color=#f8f8f2] [/color][color=#ff79c6]->[/color][color=#ff79c6] [/color][color=#8be9fd]i32[/color][color=#f8f8f2] [/color][color=#ffffff]{[/color][color=#f8f8f2]
[/color][color=#f8f8f2] [/color][color=#8be9fd]let[/color][color=#f8f8f2] [/color][color=#ff79c6]mut[/color][color=#f8f8f2] max_sum [/color][color=#ff79c6]=[/color][color=#f8f8f2] [/color][color=#bd93f9]0[/color][color=#f8f8f2];[/color][color=#f8f8f2]
[/color][color=#f8f8f2] [/color][color=#8be9fd]let[/color][color=#f8f8f2] [/color][color=#ff79c6]mut[/color][color=#f8f8f2] tmp_sum [/color][color=#ff79c6]=[/color][color=#f8f8f2] [/color][color=#bd93f9]0[/color][color=#f8f8f2];[/color][color=#f8f8f2]
[/color][color=#f8f8f2] [/color][color=#ff79c6]for[/color][color=#f8f8f2] i [/color][color=#ff79c6]in[/color][color=#f8f8f2] v [/color][color=#ffffff]{[/color][color=#f8f8f2]
[/color][color=#f8f8f2] tmp_sum [/color][color=#ff79c6]=[/color][color=#f8f8f2] [/color][color=#f8f8f2]([/color][color=#f8f8f2]tmp_sum [/color][color=#ff79c6]+[/color][color=#f8f8f2] i[/color][color=#f8f8f2])[/color][color=#ff79c6].[/color][color=#8be9fd]max[/color][color=#f8f8f2]([/color][color=#bd93f9]0[/color][color=#f8f8f2])[/color][color=#f8f8f2];[/color][color=#f8f8f2]
[/color][color=#f8f8f2] max_sum [/color][color=#ff79c6]=[/color][color=#f8f8f2] max_sum[/color][color=#ff79c6].[/color][color=#8be9fd]max[/color][color=#f8f8f2]([/color][color=#f8f8f2]tmp_sum[/color][color=#f8f8f2])[/color][color=#f8f8f2];[/color][color=#f8f8f2]
[/color][color=#f8f8f2] [/color][color=#ffffff]}[/color][color=#f8f8f2]
[/color][color=#f8f8f2] max_sum
[/color][color=#ffffff]}[/color][/font][/td][/tr]
[/table]
我也来试试代码高亮
话说 Windows 上能识别 monospace 字体么? (上面代码是不是等宽的 [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=224544&ptid=54124]4#[/url] [i]bailong360[/i] [/b]
显示的是等宽的233 以前我也碰到过,印象中是这样?[code]@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[/code]
页:
[1]