โปรแกรมค้นหาความยาวของรายการย่อยที่เพิ่มขึ้นต่อเนื่องกันอย่างเคร่งครัดหลังจากลบในPython

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums เราต้องหาความยาวสูงสุดของรายการย่อยที่เพิ่มขึ้นอย่างต่อเนื่อง เราได้รับอนุญาตให้ลบองค์ประกอบเดียวออกจากรายการได้มากที่สุด

ดังนั้นหากอินพุตเป็น nums =[35, 5, 6, 7, 8, 9, 12, 11, 26] ผลลัพธ์จะเป็น 7 เพราะถ้าเราลบ 12 ออกจาก nums รายการจะเป็น [5 , 6, 7, 8, 9, 11, 26] ยาว 7 ตัวนี้ยาวที่สุด ต่อเนื่องกัน เพิ่มเป็นรายการย่อยอย่างเคร่งครัด

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

• ถ้า nums ว่างเปล่าก็
  • คืน 0
• end :=รายการขนาดเท่ากับ nums และเติม 1
• start :=รายการขนาดเท่ากับ nums และเติมด้วย 1
• สำหรับฉันในช่วง 1 ถึงขนาดของ nums - 1 ทำ
  • ถ้า nums[i]> nums[i - 1] แล้ว
    • end[i] :=end[i - 1] + 1
• สำหรับ j ในขนาดช่วงของ nums - 2 ถึง 0, ลดลง 1, do
  • ถ้า nums[j + 1]> nums[j] แล้ว
    • start[j] :=start[j + 1] + 1
• res :=สูงสุดขององค์ประกอบของจุดสิ้นสุดและองค์ประกอบของการเริ่มต้น
• สำหรับ k ในช่วง 1 ถึงขนาดของ nums - 2 ทำ
  • ถ้า nums[k - 1]
  • res :=สูงสุดของ res และ (end[k - 1] + start[k + 1])

ตัวอย่าง

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

def solve(nums):
   if not nums:
      return 0
   end = [1 for i in nums]
   start = [1 for i in nums]

   for i in range(1, len(nums)):
      if nums[i] > nums[i - 1]:
         end[i] = end[i - 1] + 1

   for j in range(len(nums) - 2, -1, -1):
      if nums[j + 1] > nums[j]:
         start[j] = start[j + 1] + 1

   res = max(max(end), max(start))

   for k in range(1, len(nums) - 1):
      if nums[k - 1] < nums[k + 1]:
         res = max(res, end[k - 1] + start[k + 1])

   return res

nums = [35, 5, 6, 7, 8, 9, 12, 11, 26]
print(solve(nums))

อินพุต

[35, 5, 6, 7, 8, 9, 12, 11, 26]

ผลลัพธ์

7