LIS using Binary Search with PHP

LISBinarySearch.php

<?php

class Solution {

	/**
	 * @param Integer[] $nums
	 *
	 * @return Integer
	 */
	function lengthOfLIS( $arr ) {
		if ( ! $arr ) {
			return 0;
		}

		if ( count( $arr ) === 1 ) {
			return 1;
		}

		$lis = array_map( function () {
			return 1;
		}, $arr );
		$lis = array_combine( array_keys( $arr ), $lis );

		$i   = 0;
		$j   = 1;
		$max = 1;

		while ( $j < count( $arr ) && $i < count( $arr ) - 1 ) {
			if ( $arr[ $j ] > $arr[ $i ] ) {
				$new = $lis[ $i ] + 1;

				if ( $new > $lis[ $j ] ) {
					$lis[ $j ] = $lis[ $i ] + 1;

					if ( ! $max || $max < $lis[ $i ] + 1 ) {
						$max = $lis[ $i ] + 1;
					}
				}
			}

			if ( $i === $j - 1 ) {
				$i = 0;
				$j ++;
			} else {
				$i ++;
			}
		}

		return $max;
	}

	function lisBinarySearch($arr) {
		$increasingSublist = [ 0 => null ];
		$parent = [];
		$length = 0;

		for( $i = 0; $i < count( $arr ); $i ++ ) {

			$low = 1;
			$high = $length;

			while( $low <= $high ) {
				$mid = (int) ceil( ( $low + $high ) / 2 );

				if ( $increasingSublist[ $mid ] < $arr[ $i ] ) {
					$low = $mid + 1;
				} else {
					$high = $mid - 1;
				}
			}

			$pos = $low;
			$parent[ $i ] = $increasingSublist[ $pos - 1 ];
			$increasingSublist[ $pos ] = $arr[ $i ];

			if ( $pos > $length ) {
				$length = $pos;
			}
		}

		return $length;
	}
}

$arr = [ 3, 1, 5, 2, 6, 4, 9, 10, 7 ];
$solution = new Solution();
$solution->lisBinarySearch( $arr );