在Python中找到使数组排序的最大块的程序

假设我们有一个数组nums，我们必须将数组拆分成一些分区，并单独对每个分区进行排序。现在在将它们连接后，我们将得到一个排序过的数组。我们必须找出我们可以做出的最大分区数？

因此，如果输入为[3,2,4,5,5]，则输出为4，因为我们可以将分区制作为[3,2]，[4]，[5]，[5]。

要解决此问题，我们将按照以下步骤进行 −

• real：=对列表nums进行排序

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

• 无限地执行以下操作，执行

  • flag：= 真

  • tmp：=对nums [从索引p1到p2-1的子列表进行排序]

  • for j in range 0 to size of tmp 执行

    • 如果tmp [j]与real [p1 + j]不同，则执行

    • flag：=假

    • p2：= p2 + 1

    • 退出循环

    • 如果flag为真，则执行

    • 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