Python 将整组数组拆分为最小值与最大值之和的子数组

首先让我们解决一个更简单的问题.让我们运行一个数组，并为所有固定大小的窗口给出分钟和最大值.

def window_mins_maxes (size, array):
    min_values = deque()
    min_positions = deque()
    max_values = deque()
    max_positions = deque()

    for i, value in enumerate(array):
        if size <= i:
            yield (i, min_values[0], max_values[0])
            if min_positions[0] <= i - size:
                min_values.popleft()
                min_positions.popleft()

            if max_positions[0] <= i - size:
                max_values.popleft()
                max_positions.popleft()

        while 0 < len(min_values) and value <= min_values[-1]:
            min_values.pop()
            min_positions.pop()
        min_values.append(value)
        min_positions.append(i)

        while 0 < len(max_values) and max_values[-1] <= value:
            max_values.pop()
            max_positions.pop()
        max_values.append(value)
        max_positions.append(i)

    yield (len(array), min_values[0], max_values[0])

这显然需要O(size)内存.不太明显的是，处理长度为n的数组需要时间O(n).但我们可以通过摊销分析看到这一点.我们将将判断小于它的可能值的成本、稍后判断是否应该删除的某些元素的成本以及添加的成本归因于每个元素.这考虑了所有操作(尽管这不是它们发生的顺序)，并且是每个元素的固定工作量.

另请注意，解决方案的这一部分所需的内存适合O(n)以内.

到目前为止，我认为这是一个众所周知的动态规划问题.现在让我们让它更具挑战性.

我们将将分区问题作为传统的动态编程问题来解决.我们将构建一个数组best_weight，其中包含到该点为止的最佳分区，以及在该点之前结束的前一个分区的开始的prev_index.

为了构建它，我们将使用上述算法获取之前的分区，并将min_len中的一个添加到它中.如果它比之前的分区更好，我们将将其信息保存在这些数组中.然后我们将从该分区向前扫描，并进行最多max_len次扫描.然后我们继续到分区的下一个可能的开始.

完成后，我们将从该代码中找到答案.

这是它的样子:

def partition_array(numbers, min_len, max_len):
    if max_len < min_len or len(numbers) < min_len:
        return (None, None)

    best_weight = [None for _ in numbers]
    prev_index = [None for _ in numbers]

    # Need an extra entry for off of the end of the array.
    best_weight.append(None)
    prev_index.append(None)

    best_weight[0] = 0

    for i, min_value, max_value in window_mins_maxes(min_len, numbers):
        window_start_weight = best_weight[i - min_len]
        if window_start_weight is not None:
            j = i
            while j - i < max_len - min_len and j < len(numbers):
                new_weight = window_start_weight + max_value - min_value
                if best_weight[j] is None or best_weight[j] < new_weight:
                    best_weight[j] = new_weight
                    prev_index[j] = i - min_len

                if numbers[j] < min_value:
                    min_value = numbers[j]
                if max_value < numbers[j]:
                    max_value = numbers[j]
                j += 1

            # And fill in the longest value.
            new_weight = window_start_weight + max_value - min_value
            if best_weight[j] is None or best_weight[j] < new_weight:
                best_weight[j] = new_weight
                prev_index[j] = i - min_len

    if best_weight[-1] is None:
        return (None, None)
    else:
        path = [len(numbers)]
        while prev_index[path[-1]] is not None:
            path.append(prev_index[path[-1]])
        path = list(reversed(path))
        partitioned = [numbers[path[i]:path[i+1]] for i in range(len(path)-1)]
        return (best_weight[-1], partitioned)

请注意，我们对每个可能的开始和长度进行O(1)次工作.这就是时间O((max_len + 1 - min_len)*n).我们使用的数据 struct 的大小均以O(n)为上限.给出了我在 comments 中promise 的整体效率.

现在让我们测试一下.

print(partition_array([5, 8, 4, 5, 1, 3, 5, 1, 3, 1], 3, 7))
print(partition_array([1, 6, 2, 2, 5, 2, 8, 1, 5, 6], 3, 4))
print(partition_array([5, 8, 4, 5, 1, 3, 5, 1, 3, 1, 2], 4, 5))

输出是:

(12, [[5, 8, 4], [5, 1, 3], [5, 1, 3, 1]])
(16, [[1, 6, 2], [2, 5, 2, 8], [1, 5, 6]])
(None, None)