Pythonで削除した後、連続して厳密に増加する最長のサブリストの長さを見つけるプログラム

numsと呼ばれる数値のリストがあるとすると、連続して厳密に増加するサブリストの最大長を見つける必要があります。リストから最大で1つの要素を削除できます。

したがって、入力が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を入力します
• 範囲1からnums-1のサイズのiの場合、do
  • nums [i]> nums [i-1]の場合、
    • end [i]：=end [i-1] + 1
• nums-2から0の範囲サイズのjの場合、1ずつ減らします。
  • nums [j + 1]> nums [j]の場合、
    • start [j]：=start [j + 1] + 1
• res：=endの要素とstartの要素の最大値
• 範囲1からnums-2のサイズのkの場合、do
  • nums [k-1]
  • res：=resの最大値と（end [k-1] + start [k + 1]）

例

理解を深めるために、次の実装を見てみましょう-

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