Question

How to find the longest increasing not sorted subsequence (LIS) of a sequence of numbers in PHP

Answer 1

function longestIncreasingSubsequence(array $nums): int {
    $arraylen = count($nums);
    if ($arraylen === 0) {
        return 0;
    }

    $length = array_fill(0, $arraylen, 1);
    $maxLength = 1;

    for ($i = 1; $i < $arraylen; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($nums[$i] > $nums[$j]) {
                $length[$i] = max($length[$i], $length[$j] + 1);
            }
        }
        $maxLength = max($maxLength, $length[$i]);
    }

    return $maxLength;
}

$nums = [4, 5, 1, 10, 3, 9, 18, 19];

echo "Length of LIS: " . longestIncreasingSubsequence($nums) . PHP_EOL;



/*
run:

Length of LIS: 5

*/

 

70+ SQL courses for beginners and professionals