Pythonで配列をソートするための最大チャンクを見つけるプログラム

配列番号があるとすると、配列をいくつかのパーティションに分割し、それぞれを個別に並べ替える必要があります。それらを連結した後、1つのソートされた配列を取得します。作成できるパーティションの最大数を見つける必要がありますか？

したがって、入力が[3,2,4,5,5]の場合、出力は4になります。これは、[3,2]、[4]、[5]、[5]のようなパーティションを作成できるためです。

これを解決するには、次の手順に従います-

• real：=リスト番号を並べ替える

• p1：=0、p2：=1、c：=0

• 次のことを無限に行います。

  • フラグ：=True

  • tmp：=numsのサブリストを並べ替え[インデックスp1からp2-1]

  • 0からtmpのサイズまでの範囲のjについては、次のようにします

    • tmp[j]がreal[p1+ j]と同じでない場合、

      • フラグ：=False

      • p2：=p2 + 1

      • ループから出てきます

    • フラグがtrueの場合、

      • p1：=p2

      • p2：=p2 + 1

      • c：=c + 1

    • p1がnumsのサイズまたはp2>numsのサイズと同じである場合、

      • 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}

出力

4