Longest Continuous Increasing Subsequence

🏠 ⬅️ ➡️

Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing.

A continuous increasing subsequence is defined by two indices l and r (l < r) such that it is [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].

Example 1:

Input: nums = [1,3,5,4,7] Output: 3 Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3. Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element 4.

Example 2:

Input: nums = [2,2,2,2,2] Output: 1 Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly increasing.

Constraints:

  • 1 <= nums.length <= 104
  • -109 <= nums[i] <= 109
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    ! Solves the problem:
    ! Given an unsorted array of integers nums, return the length of the longest
    ! continuous increasing subsequence (i.e., subarray). The subsequence must be
    ! strictly increasing.
    implicit none

    integer :: nums(10), len_longest_subseq

    nums = [1, 3, 5, 4, 7]
    print '(I0)', len_longest_subseq(nums)

    nums = [2, 2, 2, 2, 2]
    print '(I0)', len_longest_subseq(nums)

contains

    function len_longest_subseq(nums) result(len)
        implicit none
        integer, intent(in) :: nums(:)
        integer :: len, i, j, n

        n = size(nums)
        if (n == 0) then
            len = 0
            return
        end if

        len = 1
        do i = 2, n
            if (nums(i-1) < nums(i)) then
                len = len + 1
            else
                j = i - 1
                do while (j > 1 .and. nums(j-1) >= nums(j))
                    j = j - 1
                end do
                len = max(len, i - j)
            end if
        end do
    end function len_longest_subseq

end program main
❌ Compiled
❌ Executed
❌ Correct 
module longest_continuous_increasing_subsequence

implicit none

contains

integer function longest_increasing_subsequence(nums) result(ans)

! Given an unsorted array of integers `nums`, return the length of the longest
! continuous increasing subsequence (i.e. subarray)

! A continuous increasing subsequence is defined by two indices `l` and `r` (`l < r`) such that it is
! `[nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]` and for each `l <= i < r`, `nums[i] < nums[i + 1]`.

! Example 1:
! Input: nums = [1,3,5,4,7]
! Output: 3
! Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
! Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element 4.

! Example 2:
! Input: nums = [2,2,2,2,2]
! Output: 1
! Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly increasing.

! Constraints:
! 1 <= nums.length <= 104
! -109 <= nums[i] <= 109

integer, intent(in) :: nums(:)

! dp(i) represents the length of the longest continuous increasing subsequence ending at index i
integer :: dp(size(nums))

! Initialize dp(0) to 1, as there is always a continuous increasing subsequence of length 1 ending at index 0
dp(0) = 1

! Loop through the array and update dp(i) for each index i
do i = 1, size(nums)
    ! If the current element is greater than the previous element,
    ! then the current element can be added to the subsequence
    ! ending at index i - 1, so dp(i) = dp(i - 1) + 1
    if (nums(i) > nums(i - 1)) then
        dp(i) = dp(i - 1) + 1
    ! Otherwise, the current element cannot be added to the subsequence
    ! ending at index i - 1, so dp(i) = 1
    else
        dp(i) = 1
    end if
end do

! Return the maximum value in dp
ans = maxval(dp)

end function longest_increasing_subsequence

end module longest_continuous_increasing_subsequence

! Test the longest_increasing_subsequence function with the following examples:
program test_longest_increasing_subsequence

use longest_continuous_increasing_subsequence, only: longest_increasing_subsequence

implicit none

! Examples taken from the problem statement
integer, parameter :: example1(5) = [1, 3, 5, 4, 7]
integer, parameter :: example2(5) = [2, 2, 2, 2, 2]

! Output the length of the longest continuous increasing subsequence for each example
write (*,*) "Example 1:", longest_increasing_subsequence(example1)
write (*,*) "Example 2:", longest_increasing_subsequence(example2)

end program test_longest_increasing_subsequence
🌐 Data from online sources 
def findLengthOfLCIS(nums):
    if not nums:
        return 0
    result, current = 1, 1
    for i in range(1, len(nums)):
        current = current + 1 if nums[i] > nums[i - 1] else 1
        result = max(result, current)
    return result

The algorithm works as follows:

  1. If the input array is empty, return 0.
  2. Initialize two variables: result (to hold the maximum length found so far) and current (to hold the length of the current increasing subsequence). Both are initially set to 1.
  3. Iterate through the array from index 1 to the end.
  4. For each index, if the current element is greater than the previous element, increase the length of the current increasing subsequence by 1. Otherwise, reset it to 1.
  5. Update the result with the maximum value between the current result and the current increasing subsequence length.
  6. Return the result after the iteration completes.

This algorithm has a linear time complexity, i.e., O(n), where n is the length of the input array.

🌐 Data from online sources 
int findLengthOfLCIS(vector<int>& nums) {
    if (nums.empty()) return 0;
    int result = 1, current = 1;
    for (int i = 1; i < nums.size(); ++i) {
        current = nums[i] > nums[i - 1] ? current + 1 : 1;
        result = max(result, current);
    }
    return result;
}

The algorithm works as follows:

  1. If the input array is empty, return 0.
  2. Initialize two variables: result (to hold the maximum length found so far) and current (to hold the length of the current increasing subsequence). Both are initially set to 1.
  3. Iterate through the array from index 1 to the end.
  4. For each index, if the current element is greater than the previous element, increase the length of the current increasing subsequence by 1. Otherwise, reset it to 1.
  5. Update the result with the maximum value between the current result and the current increasing subsequence length.
  6. Return the result after the iteration completes.

This algorithm has a linear time complexity, i.e., O(n), where n is the length of the input array.