Pythonで互いに素な間隔にパーティション配列を見つけるプログラム

配列numがあるとすると、-

• 左側のサブアレイの各要素は、右側のサブアレイの各要素以下です。

• 左右のサブアレイは空ではありません。

• 左側のサブアレイのサイズは可能な限り最小です。

このような分割後の残りの長さを見つける必要があります。

したがって、入力がnums =[5,0,3,8,6]の場合、左側の配列は[5,0,3]になり、右側のサブ配列は[8,6]になるため、出力は3になります。

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

• mx：=null、temp：=null、nmx：=null

• temp2：=0

• numsの各iについて、実行します

  • mxがnullと同じ場合、

    • mx：=i

    • nmx：=i

    • temp：=temp2

    • temp2：=temp2 + 1

    • 次のイテレーションに行く

  • i> =mxの場合、

    • temp2：=temp2 + 1

    • i> nmxの場合、

      • nmx：=i

    • 次のイテレーションに行く

  • それ以外の場合

    • temp：=temp2

    • temp2：=temp2 + 1

    • mx：=nmx

    • 次のイテレーションに行く

• 温度+1を返す

例

理解を深めるために、次の実装を見てみましょう-

def solve(nums):
   mx = None
   temp = None
   nmx = None
   temp2 = 0

   for i in nums:

      if(mx==None):
         mx = i
         nmx = i
         temp = temp2
         temp2+=1
         continue

      if(i>=mx):
         temp2+=1
         if(i>nmx):
            nmx = i
         continue

      else:
         temp = temp2
         temp2+=1
         mx = nmx
         continue

   return temp+1

nums = [5,0,3,8,6]
print(solve(nums))

入力

[5,0,3,8,6]

出力

3