[PHP知识库]求最长上升子序列的长度【php版】

动态规划_1
思路：以dp[i]表示以第i位结尾的递增子序列的最大长度，则 dp[i] = max(dp[i], dp[j] + 1(if nums[j] < nums[i])) (j from 0 -> i);

	function lengthOfLIS($nums) {
		$dp = array_fill(0, count($nums), 1);
		$max = 1;
		foreach($nums as $k => $num) {
			for ($i=0; $i<=$k; $i++) {
				if ($num > $nums[$i]) {
					$dp[$k] = max($dp[$k], $dp[$i]+1);
				}
			}
			$max = max($max, $dp[$k]);
		}
		return $max;
	}

贪心
实质上是找递增最慢的子序列的长度，以dp[i] = a， 表示 以a结尾的子序列的长度为i

	function lengthOfLIS_v2($nums) {
		$len = count($nums);
		if ($len == 0) return 0;
		$dp[0] = $nums[0];
		for ($i=1; $i<$len; $i++) {
			$end = count($dp) - 1;
			$start = 0;
			while ($start < $end) {
				$mid = $start + intdiv($end-$start, 2);
				if ($dp[$mid] >= $nums[$i]) {
					$end = $mid;
				} else {
					$start = $mid + 1;
				}
			}
			if ($dp[$start] > $nums[$i]) {
				$dp[$start] = $nums[$i];
				continue;
			}
			if ($dp[$start] !== $nums[$i]) {
				$dp[$start+1] = $nums[$i];
			}
		}
		return count($dp);
	}