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

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

ดังนั้นหากอินพุตเป็น nums =[30, 11, 12, 13, 14, 15, 18, 17, 32] ผลลัพธ์จะเป็น 7 เช่นเดียวกับเมื่อเราลบ 18 ในรายการเราจะได้ [11, 12, 13, 14, 15, 17, 32] ซึ่งเป็นรายการย่อยที่ยาวที่สุด ต่อเนื่องกัน เพิ่มขึ้นอย่างเคร่งครัด และมีความยาว 7

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

• n :=ขนาดของ nums

• pre :=รายการขนาด n และเติมด้วย 1s

• สำหรับฉันอยู่ในช่วง 1 ถึง n - 1 ทำ

  • ถ้า nums[i]> nums[i - 1] แล้ว

    • pre[i] :=pre[i - 1] + 1

• suff :=รายการขนาด n และเติมด้วย 1s

• สำหรับฉันอยู่ในช่วง n - 2 ถึง -1 ลดลง 1 ทำ

  • ถ้า nums[i]

    • suff[i] :=suff[i + 1] + 1

• ans :=ค่าสูงสุดของ pre และสูงสุดของ suff

• สำหรับฉันอยู่ในช่วง 1 ถึง n - 1 ทำ

  • ถ้า nums[i - 1]

    • ans :=สูงสุดของ ans และ (ก่อน[i - 1] + suff[i + 1])

• กลับมาอีกครั้ง

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

ตัวอย่าง

class Solution:
   def solve(self, nums):
      n = len(nums)
      pre = [1] * n
      for i in range(1, n - 1):
         if nums[i] > nums[i - 1]:
            pre[i] = pre[i - 1] + 1
      suff = [1] * n
      for i in range(n - 2, -1, -1):
         if nums[i] < nums[i + 1]:
            suff[i] = suff[i + 1] + 1
               ans = max(max(pre), max(suff))
               for i in range(1, n - 1):
                  if nums[i - 1] < nums[i + 1]:
                     ans = max(ans, pre[i - 1] + suff[i + 1])
               return ans
ob = Solution()
nums = [30, 11, 12, 13, 14, 15, 18, 17, 32]
print(ob.solve(nums))

อินพุต

[30, 11, 12, 13, 14, 15, 18, 17, 32]

ผลลัพธ์

7