<?php
/**
 * @Author: fql
 * @Email: fangqiulin4923@gmail.com
 * @Date: 2020-12-26 13:30
 */

namespace fql\aglorthim\dynamic;

/**
 * Class MaxContinueSum
 * @package fql\aglorthim\dynamic
 * @desc  数组最大连续子序列和,同时记录是哪些元素组成的
 */
class MaxContinueSum
{
    private $arr;
    private $elem;

    public function __construct(array $arr)
    {
        $this->arr = $arr;
    }

    public function compute(){
        $len = count($this->arr);
        if($len < 1){
            return 0;
        }
        $currentArr[] = $this->arr[0]; //初始最大值时的元素
        $maxArray  = $this->arr[0];
        $max = $this->arr[0];  //初始最大值
        $sum = $this->arr[0];  //前i个求和
        for($i = 1; $i < $len; $i++){
            $sum = $sum + $this->arr[$i];
            //如果前i个元素和小于第个元素的值
            if($sum < $this->arr[$i]){
                $sum = $this->arr[$i];
                $currentArr=[];
            }
            $currentArr[] = $this->arr[$i];
            if($sum > $max){
                $max = $sum;
            }

        }
        $this->elem = $currentArr;

        return $max;
    }

    public function getElem()
    {
        return $this->elem;
    }
}

$arr = [6,-1,3,-4,-6,9,2,-2,5,0];
$computMax = new MaxContinueSum($arr);
echo $computMax->compute();
print_r($computMax->getElem()) ;