Python에서 배열을 정렬하기 위해 최대 청크를 찾는 프로그램

<시간/>

배열 번호가 있다고 가정하고 배열을 몇 개의 파티션으로 분할하고 각각을 개별적으로 정렬해야 합니다. 이제 그것들을 연결한 후에 우리는 하나의 정렬된 배열을 얻을 것입니다. 만들 수 있는 최대 파티션 수를 찾아야 합니까?

따라서 입력이 [3,2,4,5,5] 와 같으면 [3,2], [4], [5], [5] 와 같은 파티션을 만들 수 있으므로 출력은 4가 됩니다.

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

real:=목록 번호 정렬
p1 :=0,p2 :=1, c :=0
다음을 무한히 수행하십시오.
- 플래그:=참
- tmp:=nums의 하위 목록 정렬[인덱스 p1에서 p2-1까지]
- 범위 0에서 tmp 크기까지의 j에 대해 수행
  - tmp[j]가 실수[p1+j]와 같지 않으면
    - 플래그:=거짓
    - p2 :=p2 + 1
    - 루프에서 나오다
  - 플래그가 참이면
    - p1 :=p2
    - p2:=p2+1
    - c :=c + 1
  - p1이 숫자의 크기와 같거나 p2> 숫자의 크기와 같으면
    - 반환 c

예시

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

def solve(nums):
   real=sorted(nums)
   p1,p2,c=0,1,0
   while True:

      flag=True
      tmp=sorted(nums[p1:p2])
      for j in range(len(tmp)):
         if tmp[j]!=real[p1+j]:
            flag=False
            p2+=1
            break

      if flag:
         p1,p2=p2,p2+1
         c+=1
      if p1==len(nums) or p2>len(nums):
         return c

nums = [3,2,4,5,5]
print(solve(nums))

입력

{3,2,4,5,5}