Chương trình tìm độ dài của danh sách con tăng liên tục dài nhất sau khi xóa bằng Python

Giả sử chúng ta có một danh sách các số được gọi là num, chúng ta phải tìm độ dài tối đa của một danh sách con tăng dần liền kề. Chúng tôi được phép xóa nhiều nhất một phần tử khỏi danh sách.

Vì vậy, nếu đầu vào là nums =[35, 5, 6, 7, 8, 9, 12, 11, 26], thì đầu ra sẽ là 7, bởi vì nếu chúng ta loại bỏ 12 khỏi nums, danh sách sẽ là [5 , 6, 7, 8, 9, 11, 26], độ dài là 7, đây là danh sách con dài nhất, liền kề, tăng dần.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu nums trống, thì
  • trả về 0
• end:=một danh sách có kích thước giống như nums và điền bằng 1
• start:=một danh sách có kích thước giống như nums và điền bằng 1
• đối với tôi trong phạm vi từ 1 đến kích thước là nums - 1, thực hiện
  • nếu nums [i]> nums [i - 1], thì
    • end [i]:=end [i - 1] + 1
• cho j trong phạm vi kích thước nums - 2 đến 0, giảm 1, thực hiện
  • nếu nums [j + 1]> nums [j], thì
    • start [j]:=start [j + 1] + 1
• res:=tối đa các phần tử của phần cuối và phần tử của phần đầu
• đối với k trong phạm vi 1 đến kích thước là nums - 2, thực hiện
  • nếu nums [k - 1]
  • res:=tối đa của res và (end [k - 1] + start [k + 1])

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

7