โปรแกรมค้นหาความยาวของลำดับย่อยที่ยาวที่สุดจากรายการที่กำหนดในPython

สมมติว่าเรามีรายการของตัวเลขที่เรียกว่า nums เราต้องหาขนาดของลำดับย่อยที่ยาวที่สุดโดยที่ผลต่างระหว่างตัวเลขสองตัวที่ต่อเนื่องกันสลับกันระหว่างค่าบวกและค่าลบ และความแตกต่างแรกอาจเป็นบวกหรือลบก็ได้

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[6, 10, 4, 2, 3, 9, 4, 7] ผลลัพธ์จะเป็น 6 เนื่องจากลำดับถัดไปที่เป็นไปได้คือ [6, 10, 2, 9, 4 , 7] และความแตกต่างคือ [4, -8, 7, -5, 3].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ &minuS;

• n :=ขนาดของ nums
• dp :=รายการขนาด 2n และเติม 1
• ตอบ :=0
• สำหรับ i ในช่วง 0 ถึง n ให้ทำ
  • สำหรับ j ในช่วง 0 ถึง i ทำ
    • ถ้า nums[j]
    • dp[i, 0] =สูงสุดของ dp[i, 0] และ (dp[j, 1] + 1)
  • มิฉะนั้น เมื่อ nums[j]> nums[i] แล้ว
    • dp[i, 1] =สูงสุดของ dp[i, 1] และ (dp[j, 0] + 1)
• ans =สูงสุดของ ans, dp[i, 0] และ dp[i, 1])

ตัวอย่าง (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

class Solution:
   def solve(self, nums):
      n = len(nums)
      dp = [[1] * 2 for _ in range(n)]
      ans = 0
      for i in range(n):
         for j in range(i):
            if nums[j] < nums[i]:
               dp[i][0] = max(dp[i][0], dp[j][1] + 1)
            elif nums[j] > nums[i]:
               dp[i][1] = max(dp[i][1], dp[j][0] + 1)
         ans = max(ans, dp[i][0], dp[i][1])
      return ans
ob = Solution()
nums = [6, 10, 4, 2, 3, 9, 4, 7]
print(ob.solve(nums))

อินพุต

[6, 10, 4, 2, 3, 9, 4, 7]

ผลลัพธ์

6