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 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告