Skip to content

Instantly share code, notes, and snippets.

@oceangravity
Created December 2, 2021 11:49
Show Gist options
  • Save oceangravity/1dbf7be6fe561b73629d593f5e30bc7a to your computer and use it in GitHub Desktop.
Save oceangravity/1dbf7be6fe561b73629d593f5e30bc7a to your computer and use it in GitHub Desktop.
Have the function LongestIncreasingSequence(arr) take the array of positive integers stored in arr and return the length of the longest increasing subsequence (LIS). A LIS is a subset of the original list where the numbers are in sorted order, from lowest to highest, and are in increasing order. The sequence does not need to be contiguous or uni…
<?php
/**
* Longest Increasing Sequence
* Have the function LongestIncreasingSequence(arr) take the array of positive integers stored in arr
* and return the length of the longest increasing subsequence (LIS). A LIS is a subset of the original list
* where the numbers are in sorted order, from lowest to highest, and are in increasing order.
* The sequence does not need to be contiguous or unique, and there can be several different subsequences.
* For example: if arr is [4, 3, 5, 1, 6] then a possible LIS is [3, 5, 6], and another is [1, 6].
* For this input, your program should return 3 because that is the length of the longest increasing subsequence.
*
*/
function ArrayChallenge($arr)
{
$longest = 0;
for ($x = 0; $x < count($arr); $x++) {
$len = 1;
$current = $arr[$x];
for ($i = $x; $i < count($arr); $i++) {
if ($arr[$i] > $current) {
$len++;
$current = $arr[$i];
}
}
if ($len > $longest) {
$longest = $len;
}
}
// code goes here
return $longest;
}
// keep this function call here
echo ArrayChallenge(fgets(fopen('php://stdin', 'r')));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment