0300-longest-increasing-subsequence.rb

# frozen_string_literal: true

# 300. Longest Increasing Subsequence
# https://leetcode.com/problems/longest-increasing-subsequence
# Medium

=begin
Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
=end

# @param {Integer[]} nums
# @return {Integer}
deflength_of_lis(nums)
tails=Array.new
k=0
nums.eachdo |num|
start,finish=0,k
whilestart != finish
mid=(start + finish) / 2
iftails[mid] < num
start=mid + 1
else
finish=mid
end
end
tails[start]=num
k += 1ifstart == k
end
k
end

# **************** #
# TEST #
# **************** #

require"test/unit"
classTest_length_of_lis < Test::Unit::TestCase
deftest_
assert_equal4,length_of_lis([10,9,2,5,3,7,101,18])
assert_equal4,length_of_lis([0,1,0,3,2,3])
assert_equal1,length_of_lis([7,7,7,7,7,7,7])
end
end