Python에서 연속적으로 증가하는 하위 목록의 길이를 찾는 프로그램

<시간/>

nums라는 숫자 목록이 있다고 가정하고 목록에서 하나 또는 0개의 요소를 제거할 수 있을 때 연속적으로 엄격하게 증가하는 하위 목록의 최대 길이를 찾아야 합니다.

따라서 입력이 nums =[30, 11, 12, 13, 14, 15, 18, 17, 32]와 같으면 출력은 7이 됩니다. 목록에서 18을 제거하면 [11, 12, 13, 14, 15, 17, 32] 가장 길고 연속적이며 엄격하게 증가하는 하위 목록이며 길이는 7입니다.

이 문제를 해결하기 위해 다음 단계를 따르겠습니다-

n :=숫자 크기
pre :=크기가 n인 목록과 1로 채우기
범위 1에서 n - 1까지의 i에 대해 수행
- nums[i]> nums[i - 1]이면
  - 사전[i] :=사전[i - 1] + 1
suff :=크기가 n이고 1로 채워진 목록
범위 n - 2에서 -1의 i에 대해 1 감소, 수행
- nums[i]
  - suff[i] :=suff[i + 1] + 1
ans :=pre의 최대값과 suff의 최대값의 최대값
범위 1에서 n - 1까지의 i에 대해 수행
- nums[i - 1]
  - ans :=ans의 최대값 및 (pre[i - 1] + suff[i + 1])
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

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]