มีรายการ nums แบ่งเป็นสับลิสต์ เรียงแต่ละสับลิสต์ แล้วรวมกันได้รายการเรียงทั้งหมด หาจำนวนสับลิสต์มากที่สุด
เช่น nums=[4,3,2,1,7,5] ให้ 2 แบ่ง [4,3,2,1] และ [7,5]
ขั้นตอนการแก้ปัญหา
- เปรียบเทียบ prefix sum ของ nums กับ sorted(nums)
- ทุกครั้งที่ prefix sum เท่ากัน = จบสับลิสต์ได้
- นับจุดตัด
ตัวอย่างโค้ด
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
