将整数数组拆分为具有 min 和 max 之间最大差异的子数组

Question

我正在尝试找到有效解决这个问题的算法：

给定一个未排序的数字数组，需要将其分成长度从a到b的多个子数组，使得每个子数组中的最小和最大数字的差值之和最大。必须保留数字的顺序。

示例：

a = 3, b = 7
input: [5, 8, 4, 5, 1, 3, 5, 1, 3, 1]
answer: [[5, 8, 4], [5, 1, 3], [5, 1, 3, 1]] (diff sum is 12)

a = 3, b = 4
input: [1, 6, 2, 2, 5, 2, 8, 1, 5, 6]
answer: [[1, 6, 2], [2, 5, 2, 8], [1, 5, 6]] (diff sum is 16)

a = 4, b = 5
input: [5, 8, 4, 5, 1, 3, 5, 1, 3, 1, 2]
answer: splitting is impossible

到目前为止我想出的唯一解决方案是尝试所有可能的子数组组合。

from collections import deque

def partition_array(numbers, min_len, max_len):
  max_diff_subarray = None

  queue = deque()

  for end in range(min_len - 1, max_len):
    if end < len(numbers):
      diff = max(numbers[0:end + 1]) - min(numbers[0:end + 1])
      queue.append(Subarray(previous=None, start=0, end=end, diff_sum=diff))

  while queue:
    subarray = queue.popleft()

    if subarray.end == len(numbers) - 1:
      if max_diff_subarray is None:
        max_diff_subarray = subarray
      elif max_diff_subarray.diff_sum < subarray.diff_sum:
        max_diff_subarray = subarray
      continue

    start = subarray.end + 1

    for end in range(start + min_len - 1, start + max_len):
      if end < len(numbers):
        diff = max(numbers[start:end + 1]) - min(numbers[start:end + 1])
        queue.append(Subarray(previous=subarray, start=start, end=end, diff_sum=subarray.diff_sum + diff))
      else:
        break

  return max_diff_subarray

class Subarray:
  def __init__(self, previous=None, start=0, end=0, diff_sum=0):
    self.previous = previous
    self.start = start
    self.end = end
    self.diff_sum = diff_sum

numbers = [5, 8, 4, 5, 1, 3, 5, 1, 3, 1]
a = 3
b = 7
result = partition_array(numbers, a, b)
print(result.diff_sum)

有没有更省时的解决方案？

Answer 1

有没有更省时的解决方案？

简短的问题，简短的回答：

是的，有比您在问题中提供的暴力方法代码更省时的解决方案。

---

下面，仅作为可能的优化的更长列表的示例，提供了一些如何提高所提供代码的效率的建议：

一种最明显的方法是将 Python 代码转换为 C 代码并运行编译后的可执行文件而不是 Python 脚本。

算法还有改进的空间，例如，利用有关最小必要块数的可用信息来实现代码添加，您可以通过将列表长度

n

除以

b

值来计算，以便跳过检查每个新添加的块都位于列表末尾，以节省一些时间。

您还可以考虑实现一个字典来快速调用块的计算值，以便跳过该值的计算（如果在之前的暴力算法迭代中已经完成了该计算）。