批处理之家 » 出题挑战 » 不限语言解决“最大子列和问题”

老刘1号 发表于 2019-10-30 09:33

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

[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]

xczxczxcz 发表于 2019-10-30 13:05

凑个数[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]========说实话 都没弄清题意 ===========

bailong360 发表于 2019-10-30 18:08

记得以前做过这道题[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]

bailong360 发表于 2019-10-30 21:58

[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 字体么? (上面代码是不是等宽的

老刘1号 发表于 2019-10-30 22:10

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=224544&ptid=54124]4#[/url] [i]bailong360[/i] [/b]


    显示的是等宽的233

WHY 发表于 2019-10-30 22:14

以前我也碰到过，印象中是这样？[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]

查看完整版本: 不限语言解决“最大子列和问题”