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

在Python中，我们可以通过一些方法来找出使数组排序的最大块，本文将介绍几种方法：

方法一：暴力枚举

暴力枚举是最简单的方法，它的思路是遍历整个数组，对于每一个子数组都判断它是否为非递增子数组。当遇到非递增子数组时，就将它之前的所有子数组视为一个块，直到扫描完整个数组。

def maxChunk(arr):
    n = len(arr)
    res = 0
    for i in range(n):
        curMax = arr[i]
        flag = True
        for j in range(i + 1, n):
            if arr[j] > curMax:
                curMax = arr[j]
            else:
                if flag:
                    res += 1
                    flag = False
        if flag:
            res += 1
    return res

方法二：贪心算法

贪心算法是一种效率较高的算法，它的思路是：遍历整个数组，尽可能多的将递增的数添加到同一块中，遇到非递增的数就将它视为一个新的块。

def maxChunk(arr):
    curMax, res = 0, 0
    for i, num in enumerate(arr):
        curMax = max(curMax, num)
        if curMax == i:
            res += 1
    return res

方法三：数学方法

我们还可以使用数学方法来找出使数组排序的最大块，我们需要将数组按照下标从小到大排序，然后遍历整个数组，求出当前的最大值，当最大值等于当前下标时，说明当前的块可以与之前的块合并。

def maxChunk(arr):
    tmp = [(val, idx) for idx, val in enumerate(arr)]
    tmp.sort(key = lambda x: x[1])
    res, curMax = 0, -1
    for val, idx in tmp:
        curMax = max(curMax, val)
        if curMax == idx:
            res += 1
    return res