PHP Coding Puzzle 5 : Find the Length of the Longest Increasing Subsequence

Possible solution

Here’s one way to solve the problem:

/**
 * @param int[] $nums
 *
 * @return int
 */
function lengthOfLIS(array $nums): int
{
  $n = count($nums);

  // Initialize an array to keep track of the length of the longest increasing subsequence ending at each index
  $dp = array_fill(0, $n, 1);

  // Loop through all indices in the array
  for ($i = 1; $i < $n; $i++) {
    // Loop through all previous indices
    for ($j = 0; $j < $i; $j++) {
      // If the value at the current index is greater than the value at the previous index,
      // update the length of the longest increasing subsequence ending at the current index
      if ($nums[$i] > $nums[$j]) {
        $dp[$i] = max($dp[$i], $dp[$j] + 1);
      }
    }
  }

  // Return the maximum length of any longest increasing subsequence
  return max($dp);
}

The function uses a dynamic programming approach to find the length of the longest increasing subsequence in the array. It initializes an array $dp to keep track of the length of the longest increasing subsequence ending at each index. It sets each value in $dp to 1, since the longest increasing subsequence ending at any index is at least 1 (i.e., the value itself).

It then loops through all indices in the array, and for each index, it loops through all previous indices. If the value at the current index is greater than the value at the previous index, it updates the length of the longest increasing subsequence ending at the current index to be the maximum of its current value and the length of the longest increasing subsequence ending at the previous index plus 1.

At the end of the loops, the function returns the maximum value in $dp, which is the length of the longest increasing subsequence in the array.