连续子数组的最大和

剑指Offer - PHP /

题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

分析

这是一道动态规划题。
使用一个数组$sum[]来存储到达每个元素时的和，使用一个变量$max来维持最大连续子序列的和。
每个元素的和是当前元素值与当前元素值+上一个元素的连续子序列的和的最大值。

	6	-3	-2	7	-15	1	2	2
0	6
1		max(-3,-3+6)=3
2			max(-2,-2+3)=1
3				max(7,7+1)=8
4					max(-15,-15+8)=-7
5						max(1,1+(-7))=1
6							max(2,2+1)=3
7								max(2,2+3)=5

代码

<?php

namespace app\index\controller;

class Test
{
    // 测试
    public function test()
    {
        $array = [6, -3, -2, 7, -15, 1, 2, 2];
        $this->FindGreatestSumOfSubArray($array);
    }

    /**
     * @param $array  输入数据
     * @return mixed  返回最大和
     */
    function FindGreatestSumOfSubArray($array)
    {
        $sum[]  = $array[0];   // 记录遍历到各个元素时的和，初始值为数组第一个值
        $max    = $array[0];   // 维持最大连续子序列的和
        $length = count($array);

        for ($i = 1; $i < $length; $i++) {
            $sum[] = max($array[$i], $array[$i] + $sum[$i - 1]);
            $max   = max($max, $sum[$i]);
        }

        return $max;
    }
}