具有相等总和的最大子数组数

Question

我在一次采访中被问到这个问题。给定一个整数数组（具有正值和负值），我们需要找到具有相等总和的不相交子数组的最大数量。

例子：

输入：[1,2,3]输出：2{因为我们最多有2个子数组，总和=3，即[1,2]，[3]}

输入： [2 2 2 -2] 输出 ： 2 {两个子数组，每个子数组的总和 = 2，即 [2]，[2， 2， -2]}

我的方法

我想到的第一种方法是找到前缀和数组，然后以每个元素（前缀[i]）为目标，找到和=前缀[i]的子数组数。

但这在负数的情况下失败了。如何处理负面案例？

编辑完整数组必须包含这些子数组。这就是为什么在示例2中，我们得到2作为输出，而不是3（[2]、[2]，[2]）。

Answer 1

_{我假设整个数组需要覆盖子数组。}

经过一段时间的思考，我非常有信心，以下O（n^2）算法应该是有效的：

public static int maxSplitCount(int[] a) {

    int res = 0; // highest sub-array count found so far

    int sum = 0; // sum within each sub-array
    for (int i = 0; i != a.length; ++i) { // iterate over any possible front sub-array...
        sum += a[i]; // ...and determine its element-sum

        int arrayCount = 1; // count the sub-arrays with this element-sum
        int currentSum = 0; // sum in the currently traversed sub-array
        for (int j = i + 1; j != a.length; ++j) {
            currentSum += a[j];

            // if sum matches, we found the end of the currently traversed sub-array
            if (currentSum == sum) {
                arrayCount += 1;
                currentSum = 0;
            }
        }

        // tricky part (see below)
        if (currentSum > 0 || currentSum % sum != 0) {
            continue;
        }

        arrayCount += currentSum / sum;
        if (arrayCount > res) {
            res = arrayCount;
        }
    }

    return res;
}

在“棘手的部分”之前，这应该是您在第一次尝试时可能会想到的天真实现。使用负数本身没有问题。它们将简单地减少INF tSum，要求后面的元素再次适当地增加它，直到最终-通过收集足够的元素-电流Sum==sum。在某些时候（在初始化之外）电流Sum也可能是0甚至是负数。这也没问题。特别是，电流Sum为0仅表示我们当前正在遍历一个子数组，该子数组本身具有前导0-sum子数组。

出现问题的唯一情况是当我们在数组的末尾有剩余元素时，它们一起没有形成一个完整的子数组，其中包含元素-sumsum-i. e.在最后一次内部循环迭代后，电流-值不是0。开始了“棘手的部分”，我们必须区分三种情况。剩余元素的总和（即电流-值）是

1. 阳性。但是，显然，其余元素本身不能以一种产生具有元素和和的子数组的方式进行拆分（否则，这将在刚刚完成的内部for循环中发生）。
2. 负电流求和百和 ！= 0。由于直到其余元素的所有元素都有一个 sum 的倍数作为元素和，因此整个数组没有像 total element-sum 这样的倍数。
3. 负电流求和百分比总和 == 0。

每个都有各自的原因，1）和2）渲染情况，在这些情况下，我们根本无法拥有当前值为sum的适当分区。然而，在3）中，我们有一些负面的“开销”，我们可以完美地平衡一些（一个或多个）之前找到的子数组，每个子数组都包含元素-和sum，总共形成一个0-sum子数组。然后可以简单地将该子数组视为附加到前面的子数组（再次使用元素-和sum），构建一个仍然大小sum的联合子数组。

让我们以第二个示例为例，看看当我们处于外部迭代＜code＞i=0＜/code＞中，并且刚刚将内部＜code＞留给＜/code＞循环时。我们有arrayCount=3（三个单独的[2]-数组）和currentSum=-2，现在我们可以将“剩余元素”（只有-2）与最后的[2]数组连接起来，形成一个0和数组，并将其附加到最后一个[2]数组。我们在＜code＞arrayCount＜/code＞中计算的合并中总共丢失了一个数组。这由arrayCount=currentSum/sum考虑（请注意，此时，当前和为非正，因此除法为非正，=实际上正确地递减了阵列计数）。请注意，在该行之后，如果剩余元素具有更高的负和，则阵列计数甚至可能为负（或0）-如-10（或-6）-但这仅告诉我们，整个阵列的总元素和与当前值和具有相反的符号（或是0>/code>），这再次告诉我们没有合适的分区。然而，在这种情况下，arrayCount

如果您特别注意，您可能想知道在某些外部迭代sum=0中会发生什么。这目前会导致异常，但您可以在“棘手部分”之前轻松添加解决方法：

if (sum == 0) {
    if (currentSum == 0 && arrayCount > res) {
        res = arrayCount;
    }
    continue;
}

或者等效的东西。事实上，在这种情况下，我们实际上无法用任何数量的先前sum-sum数组来平衡负“开销”（因为sum是0），因为-就像上面的案例2）-电流Sum不是sum的倍数。

既然我们已经在考虑总和= 0，那么关于总和的是什么

< sup>1:当然，此时我们可以简化一些逻辑表达式和< code > if -语句，同时考虑< code>sum = 0和< code>sum

Answer 2

更新：OP澄清了整个阵列必须划分为完整的子阵列。因此，这篇文章的前半部分是一个完整的答案，但后半部分可能仍然是这个问题的一个解决方案。

如果我们使用整个阵列，问题可以在＜code＞O（n）

如果我们不使用整个数组，问题就更难了。有一个O(n^2)解决方案，其中计算所有子阵列和，按右endpoint对和相等的子阵列进行排序，并使用贪婪间隔调度。我不知道这是否是最佳选择，但我很想知道是否有更好的解决方案。

全数组分区情况

这里的精确问题定义是找到最长的点序列[x_0，x_1，…x_m]的长度，使得0

假设我们已经将数组的和计算为S。然后，我们可以将A分解为等和的k，当且仅当（k除以S，如果我们将S/k，2S/k，…，kS/k视为A前缀和的子序列）。一种简单的方法是保持一个运行求和：如果我们的运行求和＜code＞r＜code＞除以＜code＞S＜code＞，那么将＜code＞2S／r＜／code＞保存在hashmap中，作为‘我们正在搜索的求和’。如果我们的当前和是我们一直在搜索的，则将该子序列中的下一个数字保存为“我们正在搜索的和”，除非我们已经到达该序列的末尾。

例如，假设S是32。然后，A可以被划分为8，当且仅当4、8、12、16、20、24、28A的前缀和的子序列出现时（32始终出现在末尾）。因此，一旦我们将4视为前缀和，我们将检查它是否除以S，然后将8保存到前缀和的搜索集中。我们还保留了一个助手字典，将8映射到4，这样，在找到8作为前缀和后，我们知道84是下一个要查找的前缀和。

Python代码：

def best_full_partition(nums: List[int]) -> int:
    """Given a list of integers (positive or negative) 'nums',
    return the maximum number of disjoint equal sum subarrays we can
    partition nums into (using all elements)"""

    total = sum(nums)

    # Special case where total sum is 0
    if total == 0:
        # Count the number of times 0 is a partial sum
        answer = 0
        current_sum = 0
        for x in nums:
            current_sum += x
            if current_sum == 0:
                answer += 1
        return answer

    best_found = 1

    # Prefix sums we're trying to find; all share common factor with total
    looking_for = set()

    """ Map from prefix sums to the common factor/original prefix sum.
        There may be several: e.g. total/6 and total/3 may be targets
        of 2*total/3. """
    looking_to_original_sums = collections.defaultdict(set)

    current_sum = 0

    for x in nums:
        current_sum += x
        if current_sum == 0:
            continue

        if current_sum in looking_for:
            for original_sum in looking_to_original_sums[current_sum]:
                new_target = current_sum + original_sum

                # If we've found all matches in this chain
                if new_target == total:
                    best_found = max(best_found, total // original_sum)
                    continue

                looking_for.add(new_target)
                looking_to_original_sums[new_target].add(original_sum)

            looking_to_original_sums.pop(current_sum)
            looking_for.discard(current_sum)

        # Check if current sum is a divisor of full array sum
        if total % current_sum == 0:
            # If this splits array in half by sum, we've reached its end
            if 2 * current_sum == total:
                best_found = max(best_found, 2)
            else:
                # Add the next multiple of this sum to our search set
                looking_for.add(2 * current_sum)
                looking_to_original_sums[2 * current_sum].add(current_sum)

    return best_found

这需要O（n）时间，这是最优的，和O（n）空间。

部分数组分区

这种情况更难，因为有效子数组和的条件更少。诀窍是只计算所有子数组的和。我们制作一个哈希图，将每个和映射到其子数组的索引边界，因此sum（A[L， L 1，... R]）映射到[L， R]。由于存在重复，我们保留一个生成该和的所有间隔的列表，并生成该列表以按正确的endpoint排序。

现在，我们可以使用最早截止日期优先调度，也称为贪婪调度，来找到我们可以从该列表中获得的最大间隔数，而不会出现重叠。这两个步骤都需要二次时间。也许可以改进这一点，但我不知道如何做到这一点。

Python代码：

def best_partial_partition(nums: List[int]) -> int:
    """Given a list of integers (positive or negative) 'nums',
    return the maximum number of disjoint equal sum subarrays we can
    create from nums (using all elements is not required)"""

    n = len(nums)

    best_found = 1

    # For each subarray sum, stores a list of all subarrays with that sum
    # Sorted by right endpoint, both ends inclusive
    sum_to_intervals = collections.defaultdict(list)

    for right_end in range(n):
        curr_sum = 0
        for left_end in reversed(range(right_end+1)):
            curr_sum += nums[left_end]
            sum_to_intervals[curr_sum].append([left_end, right_end])

    # Use greedy interval scheduling to get most intervals

    for interval_list in sum_to_intervals.values():
        # Can skip if we know no improvement is possible here
        if len(interval_list) <= best_found:
            continue

        curr_len = 0
        curr_right_end = -1
        for left, right in interval_list:
            if left > curr_right_end:
                curr_len += 1
                curr_right_end = right

        best_found = max(best_found, curr_len)

    return best_found

这在＜code＞O（n^2）＜/code＞时间内运行。

编辑：修复了当数组和为0时完整分区求解器中的错误；感谢@josejuan指出这一点。这种情况需要单独处理，以避免被零除。

Answer 3

首先，假设它们可以是非连续的元素

可能没有有效的算法（如果有，P=NP），那么，简单地检查所有可能的组合（分区）。

如果< code>partitions是一个返回给定集合的所有分区的函数，那么您的问题就可以用以下方法解决:

static Optional<List<List<Integer>>> maximumSubarraysEqSum(List<Integer> xs) {
  return
    // all indexes partitions
    partitions(IntStream.range(0, xs.size()).mapToObj(x -> x).collect(toList()))
    // with all groups with same sum
    .stream().filter(zs -> zs.stream().mapToInt(ys -> ys.stream().mapToInt(xs::get).sum()).distinct().count() == 1L)
    // sorting by size desc
    .sorted((zs, ys) -> Integer.compare(ys.size(), zs.size()))
    // first (or all with same size if you want, ...)
    .findFirst()
    // map indexes to values
    .map(zs -> zs.stream().map(ys -> ys.stream().map(xs::get).collect(toList())).collect(toList()));
}

跑步

public static void main(String... args) {
    System.out.println("    " + maximumSubarraysEqSum(List.of(1, 2, 3)));
    System.out.println("    " + maximumSubarraysEqSum(List.of(2, 2, 2, -2)));
    System.out.println("    " + maximumSubarraysEqSum(List.of(3, 4)));
}

输出为

Optional[[[1, 2], [3]]]
Optional[[[2, 2, -2], [2]]]
Optional[[[3, 4]]]

其次，假设它们必须是连续的元素

第一个子数组设置了什么是可能的和，然后对于每个可能的“第一个和”，我们检查组的数量

static int maxSubarrayEqSum(List<Integer> xs) {
    // possible sizes for the first subarray
    return IntStream.range(1, xs.size() + 1)
            // with that sum count (if exists) how many subarrays match
            .map(sz -> countMaxSubArrayEqSum(0, xs, xs.stream().limit(sz).mapToInt(x -> x).sum()))
            // get the maximum number
            .max()
            .getAsInt();
}

计算最大子阵列是为了得到第一个可能的和

static int countMaxSubArrayEqSum(int from, List<Integer> xs, int sz) {
    int acc = 0;
    for(int i = from; i < xs.size(); i++) {
        acc += xs.get(i);
        if(acc == sz) {
            if(i == xs.size() - 1)
                return 1;
            int count = countMaxSubArrayEqSum(i + 1, xs, sz);
            if(count > 0)
                return count + 1;
        }
    }
    return 0;
}

连续序列O（n^2）的最优解

相反，我们可以获得maxSplit值（组的最大值），检查xs是否可以除以|xs|，|xs|-1，|xs|-2，...，1组。

static int maxSplit(int [] xs) {

    // sum all
    int S = 0;
    for(int i = 0; i < xs.length; i++)
        S += xs[i];

    // try every possible number of groups
    for(int i = xs.length; i > 1; i--)
        if(S % i == 0 && maxSplitFit(xs, i, S / i))
            return i;

    return 1;
}

xs可以分为k组，如果我们可以使用贪婪的策略

static boolean maxSplitFit(int [] xs, int k, int s) {

    int groupsCount = 1;
    int acc = 0;

    // look for (not final) groups summing S/k
    int i = 0;
    while(i < xs.length - 1 && groupsCount < k) {
        acc += xs[i];
        if ((s == 0 && acc == 0) // divide by 0
         || (s != 0 && s * groupsCount == acc)) // S/k
            groupsCount++;
        i++;
    }

    // if there are not enough groups then it is not possible
    if(groupsCount != k)
        return false;

    // the last group must contains all remaining elements
    while(i < xs.length)
        acc += xs[i++];

    // S/k for every group
    return s * k == acc;
}

一边

获取所有分区的可能函数可以是

static <T> List<List<List<T>>> partitions(List<T> set) {
    // last element
    T element = set.get(set.size() - 1);

    if (set.size() == 1)
        return singletonList(singletonList(singletonList(element)));

    List<List<List<T>>> current = new ArrayList<>();

    // it could be in any of previous groups or in a new one

    // add on every previous
    for (List<List<T>> p : partitions(set.subList(0, set.size() - 1))) {
        // every candidate group to place
        for (int i = 0; i < p.size(); i++) {
            List<List<T>> b = new ArrayList<>(p);
            b.add(i, new ArrayList<>(b.remove(i)));
            b.get(i).add(element);
            current.add(b);
        }
        // add singleton
        List<List<T>> b = new ArrayList<>(p);
        b.add(singletonList(element));
        current.add(b);
    }

    return current;
}