动态规划 (案例二,最大子串问题)

<?php
/**
 * @Author: fql
 * @Email: fangqiulin4923@gamil.com
 * @Date: 2020-07-16 20:11
 */

namespace fql\aglorthim;

/**
 * Class Dynamic
 * @package fql\aglorthim
 * 动态规划案例:给定数组arr，返回arr的最长递增子序列的长度，比如arr=[2,1,5,3,6,4,8,9,7]，最长递增子序列为[1,3,4,8,9]返回其长度为5.
 */
class DynamicSubArray
{
    private $dp;
    private $arr;
    private $len;

    public function __construct( array $array)
    {
        $this->arr = $array;
        $this->len = count($this->arr);
        for($i = 1 ; $i < $this->len; $i++){
            $this->step($i);
        }

    }

    public  function step($n){

        if($n >= $this->len){
            return;
        }
        if($n == 1){
            $this->dp[$n -1 ] = 1;
        }
        //如果array[i - 1] < 如果array [i], 则 dp[i] = dp[i - 1] +1;
        //如果array[i - 1] >= 如果array [i],则 dp[i] = dp[i - 1];
       if($this->arr[$n - 1 ] < $this->arr[$n]){
           $this->dp[$n] = $this->dp[$n -1 ] + 1;
       }else{
           $this->dp[$n] = $this->dp[$n -1 ];
       }
    }

    public function maxLen(){
       return  $this->dp[$this->len - 1];
    }
}


$dp = new DynamicSubArray([2,1,5,3,6,4,8,9,7]);
echo $dp->maxLen();