java - 总和相等的子数组的最大数量

Question

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

示例:

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

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

我的方法

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

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

EDIT 完整的数组必须被这些子数组覆盖。这就是为什么在示例 2 中我们得到 2 作为输出而不是 3 ([2],[2],[2])。

Answer 1

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

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

如果 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;
}