สมมติว่าเรามีรายการตัวเลข เราต้องหาความยาวของการเพิ่มขึ้นที่ยาวที่สุดตามมา ดังนั้นหากอินพุตเป็นเหมือน [6, 1, 7, 2, 8, 3, 4, 5] ผลลัพธ์จะเป็น 5 เนื่องจากลำดับการเพิ่มขึ้นที่ยาวที่สุดคือ [2,3,4,5,6]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สร้างอาร์เรย์ชื่อก้อยซึ่งมีขนาดเท่ากับ nums และเติมค่านี้ด้วย 0
-
ขนาด :=0
-
สำหรับแต่ละองค์ประกอบ x ในอาร์เรย์ nums -
-
ผม :=0, j :=ขนาด
-
ในขณะที่ฉันไม่เหมือนกับ j แล้ว
-
กลาง :=i + (j – i)/2
-
ถ้าก้อย[กลาง]
-
-
หาง[i] :=x
-
size :=max ofi + 1 และขนาด
-
-
ขนาดผลตอบแทน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution(object): def solve(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) return size ob = Solution() nums = [7, 2, 8, 3, 9, 4, 5, 6] print(ob.solve(nums))
อินพุต
[7, 2, 8, 3, 9, 4, 5, 6]
ผลลัพธ์
5
