Python程式：查詢移除元素後最長連續嚴格遞增子列表的長度

假設我們有一個名為nums的數字列表，我們需要找到連續嚴格遞增子列表的最大長度。我們最多可以從列表中移除一個元素。

因此，如果輸入類似於nums = [35, 5, 6, 7, 8, 9, 12, 11, 26]，則輸出將為7，因為如果我們從nums中移除12，列表將變為[5, 6, 7, 8, 9, 11, 26]，長度為7，這是最長的連續嚴格遞增子列表。

為了解決這個問題，我們將遵循以下步驟：

• 如果nums為空，則
  • 返回0
• end := 一個與nums大小相同的列表，並填充為1
• start := 一個與nums大小相同的列表，並填充為1
• 對於i從1到nums的大小-1，執行
  • 如果nums[i] > nums[i - 1]，則
    • end[i] := end[i - 1] + 1
• 對於j從nums的大小-2到0，遞減1，執行
  • 如果nums[j + 1] > nums[j]，則
    • start[j] := start[j + 1] + 1
• res := end元素和start元素中的最大值
• 對於k從1到nums的大小-2，執行
  • 如果nums[k - 1] < nums[k + 1]，則
    • res := res和(end[k - 1] + start[k + 1])中的最大值
• 返回res

示例

讓我們看看以下實現以更好地理解：

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

Arnab Chakraborty

更新於: 2021年10月19日

442 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

立即開始