Python에서 배열을 정렬하기 위해 제거할 가장 짧은 하위 배열을 찾는 프로그램

<시간/>

arr이라는 배열이 있다고 가정하고 arr의 나머지 요소가 감소하지 않는 순서로 되도록 arr의 하위 배열을 제거해야 합니다. 제거할 가장 짧은 하위 배열의 길이를 찾아야 합니다.

따라서 입력이 arr =[10,20,30,100,40,20,30,50]과 같으면 길이 3의 가장 작은 부분배열인 [100, 40, 20]을 제거할 수 있기 때문에 출력은 3이 됩니다. 그리고 이것들을 제거하면 모두 내림차순이 아닙니다[10,20,30,30,50].

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

n :=arr의 크기
arr :=arr의 왼쪽에 0을 삽입하고 오른쪽에 무한대를 삽입
A,B :=두 개의 새로운 빈 목록
p :=1, q:=arr의 크기 -2
남 :=0
p <=q인 동안 do
- arr[p-1] <=arr[p]이면
  - A 끝에 arr[p] 삽입
  - p :=p + 1
- 그렇지 않으면 arr[q] <=arr[q+1]일 때
  - B 끝에 arr[q] 삽입
  - A가 비어 있지 않고 A의 마지막 요소인 동안> B의 마지막 요소, do
    - A에서 마지막 요소 삭제
  - q :=q - 1
- 그렇지 않으면
  - 루프에서 나오다
- M :=M의 최대값 및 A의 크기 + B의 크기
n - M을 반환

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예

def solve(arr):
   n = len(arr)
   arr = [0] + arr + [float("inf")]
   A,B=[],[]
   p,q=1,len(arr)-2
   M = 0
   while p <= q:
      if arr[p-1] <= arr[p]:
         A.append(arr[p])
         p += 1
      elif arr[q] <= arr[q+1]:
         B.append(arr[q])
         while A and A[-1] > B[-1]:
            A.pop()
         q -= 1
      else:
         break
      M = max(M, len(A)+len(B))
   return n - M
arr = [10,20,30,100,40,20,30,50]
print(solve(arr))

입력

[10,20,30,100,40,20,30,50]