สมมติว่าเรามีรายการตัวเลข nums เราต้องการหาขนาดของลำดับย่อยที่ความต่างระหว่างสองตัวติดกันสลับเครื่องหมายระหว่างบวกและลบ (อาจเริ่มจากบวกหรือลบก็ได้)
เช่น ถ้าข้อมูลนำเข้าคือ nums = [6, 10, 4, 2, 3, 9, 4, 7] ผลลัพธ์จะเป็น 6 เนื่องจากลำดับย่อยหนึ่งคือ [6, 10, 2, 9, 4, 7] ความต่างคือ [4, -8, 7, -5, 3]
ขั้นตอนการแก้ปัญหา (DP 2 สถานะ)
n := len(nums)dp := array ขนาด n x 2 เติม 1โดยdp[i][0]= ยาวสุดลงท้าย i ความต่างบวก,dp[i][1]= ความต่างลบans := 0- วน
i = 0..n-1:- วน
j = 0..i-1:- ถ้า
nums[j] < nums[i]:dp[i][0] = max(dp[i][0], dp[j][1] + 1) - ถ้า
nums[j] > nums[i]:dp[i][1] = max(dp[i][1], dp[j][0] + 1)
- ถ้า
ans = max(ans, dp[i][0], dp[i][1])
- วน
- คืน
ans
ตัวอย่างโค้ด
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
