パーティション化できるサブリストの数を見つけるプログラム。指定されたリストは最終的にPythonでソートされます。

numsという番号のリストがあるとします。リストをいくつかの個別のサブリストに分割してから、各部分を並べ替えることができます。後で全体としてnumsがソートされるように、分割できるサブリストの最大数を見つける必要があります。

したがって、入力がnums =[4、3、2、1、7、5]の場合、出力は2になります。これは、[4、3、2、1]や[7、 5]

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

• count：=0
• main_sum：=0、sorted_sum：=0
• numsの各要素xおよびnumsのソートされた形式のyについて、do
  • main_sum：=main_sum + x
  • sorted_sum：=sorted_sum + y
  • main_sumがsorted_sumと同じ場合、
    • count：=count + 1
• 返品数

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

例

class Solution:
   def solve(self, nums):
      count = 0
      main_sum = sorted_sum = 0

      for x, y in zip(nums, sorted(nums)):
         main_sum += x
         sorted_sum += y
         if main_sum == sorted_sum:
            count += 1

      return count

ob = Solution()
nums = [4, 3, 2, 1, 7, 5]
print(ob.solve(nums))

入力

[4, 3, 2, 1, 7, 5]

出力

2