สมมติว่าเรามีรายการจำนวนเต็มที่ไม่เรียงลำดับ เราต้องหาลำดับต่อมาที่เพิ่มขึ้นนานที่สุด ดังนั้นหากอินพุตคือ [10,9,2,5,3,7,101,18] ผลลัพธ์จะเป็น 4 เนื่องจากลำดับที่เพิ่มขึ้นคือ [2,3,7,101]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- trail :=อาร์เรย์ที่มีความยาว 0 ถึงความยาวของ nums – 1 และเติมค่านี้ด้วย 0
- ขนาด :=0
- สำหรับ x เป็น nums
- i :=0, j :=ขนาด
- ในขณะที่ฉันไม่ใช่เจ
- กลาง :=i + (j - i) / 2
- ถ้าเทรล[กลาง]
- เส้นทาง[i] :=x
- ขนาด :=สูงสุดของ i + 1 และขนาด
- ขนาดผลตอบแทน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution(object): def lengthOfLIS(self, nums): tails =[0 for i in range(len(nums))] size = 0 for x in nums: i=0 j=size while i!=j: mid = i + (j-i)//2 if tails[mid]< x: i= mid+1 else: j = mid tails[i] = x size = max(i+1,size) #print(tails) return size ob1 = Solution() print(ob1.lengthOfLIS([10,9,2,5,3,7,101,18]))
อินพุต
[10,9,2,5,3,7,101,18]
ผลลัพธ์
4
