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 的列表，並填充 1

  • 對於 i 從 1 到 n - 1，執行以下操作：

    • 如果 nums[i] > nums[i - 1]，則

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

  • suff := 一個大小為 n 的列表，並填充 1

  • 對於 i 從 n - 2 到 -1，遞減 1，執行以下操作：

    • 如果 nums[i] < nums[i + 1]，則

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

  • ans := pre 的最大值和 suff 的最大值中的最大值

  • 對於 i 從 1 到 n - 1，執行以下操作：

    • 如果 nums[i - 1] < nums[i + 1]，則

      • ans := ans 和 (pre[i - 1] + suff[i + 1]) 中的最大值

  • 返回 ans

讓我們看看下面的實現來更好地理解：

示例

 線上演示

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

更新於: 2020年10月6日

171 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告