算法:求一个数组中总和最大的序列  


需求:给定一个数组,求出该数组连续的子集中,和最大的子集。

关键点:
该题目跟求一个数组中的最大值和最小值一样,千万不要排序。只需要使用三个临时变量暂存最大序列的起始位置,序列长度,以及当前序列和。然后跟其他序列一一比对。

#
# 求数组中指定区间元素的和
# 备注:PowerShell 有 Measure-Object,可完成该需求,
#
function Sum-Elements
{
    param($Items,$FromIndex,$Count)
    
    if($Count -le 0)
    {
        return 0
    }
    if(($Count+$FromIndex) -gt $Items.length)
    {
        throw "Count out of bound"
    }

    $sum = 0
    for ($i = $FromIndex; $i -lt $FromIndex+$Count; $i++)
    { 
        $sum += $Items[$i]
    }
    return $sum
}

$nums = @(-1,-9,-2,-1,7,1,-3,2,5,6)
$maxSum = [int]::MinValue
$maxSumFromIndex = 0
$maxSumCount=1

for ($length = 1; $length -le $nums.Count; $length++)
{ 
    for ($index = 0; $index -le $nums.Count - $length ; $index++)
    { 
        $sum = Sum-Elements -Items $nums -FromIndex $index -Count $length
        #Write-Host "MaxSum = $sum, FromIndex = $index, Count = $length"
        if($sum -gt $maxSum){
            $maxSum = $sum
            $maxSumFromIndex = $index
            $maxSumCount = $length
        }
    }
}
Write-Host "Final Result"
Write-Host "MaxSum = $maxSum, FromIndex = $maxSumFromIndex, Count = $maxSumCount"

# 打印子串结果
$endIndex = $maxSumFromIndex + $maxSumCount-1
$result = $maxSumFromIndex..$endIndex | foreach {
    $nums[$_]
 }
"({0})" -f ($result -join ",")

输出结果

Final Result
MaxSum = 18, FromIndex = 4, Count = 6
(7,1,-3,2,5,6)
×用微信扫描并分享
本文链接: https://www.pstips.net/max-sum.html
请尊重原作者和编辑的辛勤劳动,欢迎转载,并注明出处!

关于 Mooser Lee

我是一个Powershell的爱好者,创建了PowerShell中文博客,热衷于Powershell技术的搜集和分享。本站部分内容来源于互联网,不足之处敬请谅解,并欢迎您批评指正。

发表评论

电子邮件地址不会被公开。 必填项已用*标注