Python에서 제거한 후 가장 긴 연속적으로 엄격하게 증가하는 하위 목록의 길이를 찾는 프로그램

<시간/>

nums라는 숫자 목록이 있다고 가정하고 연속적으로 증가하는 하위 목록의 최대 길이를 찾아야 합니다. 목록에서 최대 단일 요소를 제거할 수 있습니다.

따라서 입력이 nums =[35, 5, 6, 7, 8, 9, 12, 11, 26]과 같으면 출력은 7이 됩니다. 왜냐하면 num에서 12를 제거하면 목록은 [5 , 6, 7, 8, 9, 11, 26], 길이는 7이며 가장 길고 연속적이며 엄격하게 증가하는 하위 목록입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

nums가 비어 있으면
- 0을 반환
end :=숫자와 크기가 같고 1로 채워지는 목록
start :=숫자와 같은 크기의 목록으로 1로 채움
범위 1에서 숫자 - 1까지의 i에 대해
- 숫자[i]> 숫자[i - 1]이면
  - 끝[i] :=끝[i - 1] + 1
숫자 범위 크기의 j에 대해 - 2에서 0, 1 감소, do
- 숫자[j + 1]> 숫자[j]이면
  - 시작[j] :=시작[j + 1] + 1
res :=끝 요소와 시작 요소의 최대값
범위 1에서 숫자 크기 - 2까지의 k에 대해
- 숫자[k - 1] <숫자[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]