300.md

✏️Leetcode之PHP版题目解析（300. Longest Increasing Subsequence）

2019-05-22 吴亲库里 库里的深夜食堂

---

✏️描述

给定一个数组，找出最长增加的子序列。

✏️题目实例

​ ****

✏️题目分析

首先他并不是求连续的，只要后面的数比前面的大，那么他就是可以被添加到子序列中的，只是说每次应该加入较小的数字，才能给后面腾出更多的位置。

 DP[i]=Max(DP[i],DP[i-1]+1)
//如果$nums[i-1]<$nums[$j],说明此时$nums[i]也能加入到子序列中           

       /**
         * @param Integer[] $nums
         * @return Integer
         */
        function lengthOfLIS($nums) {
            if(empty($nums)){
                return 0;
            }
            $res=1;
            for($i=0;$i<count($nums);$i++){
                $dp[$i]=1;
                for($j=0;$j<$i;++$j){
                    if($nums[$j]<$nums[$i]){
                        $dp[$i]=max($dp[$i],$dp[$j]+1);
                    }
                    $res=max($res,$dp[$i]);
                }
            }
            return $res;
        }

联系

​