找到数组中所有可能的子数组并求和

Question

假设数组是A={1,2,3}，现在获取此数组的所有子数组。对于每个子数组，在该子数组中找到最小值，也找到该子数组中的项目之和。最后添加所有这些值。输入无法按我想要的所有可能的子数组进行排序。

例子：

可能的子阵列包括：

{1} - min = 1, sum = 1 => min* sum = 1
{1,2} - min = 1, sum = 3 => min* sum = 3
{1,2,3} - min = 1, sum = 6 => min* sum = 6
{2} - min = 2, sum = 2 => min* sum = 4
{2,3} - min = 2, sum = 5 => min* sum = 10
{3} - min = 3, sum = 3 => min* sum = 9

最后，将所有这些值相加，得到结果=1 3 6 4 10 9=33。

约束：数组元素的范围从1到1000\u 000\u 000。数组大小从1到100\u 000。将输出作为模块7 1000\u 000\u 000返回。

这是我用O（n^2）编写的程序。我想要一个时间复杂度更低的更好的算法。

public int program(int[] A, int n) {
    int M = 7 + 1000_000_000;
    long total = 0;
    for (int i = 0; i < n; i++) {
        long sum = 0;
        int min = A[i];
        for (int j = i; j < n; j++) {
            int a = A[j];
            sum= (sum + a) % M;
            min = Math.min(min, a);
            total = (total + (min * sum) % M) % M;
        }
    }
    return (int) total;
}

输入范围：

n range is 1 to 10^6
elements in array range is 1 to 10^9

Answer 1

这个问题可以在O（n log n）中解决。

基本想法

在这个解释中，可能潜入了很多off-by-one错误，但这与这个想法无关。让m是数组的最小值。然后任何包含m的子数组都将m作为最小值，并且每个其他子数组都将完全在m之前或完全在m之后。让n是数组中的元素数，让我们将m视为索引。然后对于每个i

问题出在更新中。将这些i*A[m]*（n-m）添加到每一个可能的i将导致二次解。但正如人们可以注意到的，两边都是关于i的线性函数，这是一个重要的属性。让我们将右侧的函数重写为i*-A[m]*m n*A[m]*m。所以我们将为每个索引使用a*i b表达式。如果我们有两个线性函数a*i b和c*i d，它们的总和显然是（a c）*i（b d）-也是一个线性函数。为了结束这种优化，我们将使用一个带有两个参数的递归函数：当前处理的子数组和应用于每个元素的线性函数。

最后要解决的问题是在子阵中找到最小值，但这就是RMQ问题，可以在O（n log n）中解决。

功能

当然，为了加快速度，我们不会创建子阵列，而是传递索引。我们想要实现的伪代码：

//This uses inclusive l and exclusive r
public int program(int[] A, int l, int r, int a, int b) {
  if (r - l == 0) {
    //array of size 0 can appear in recursive calls
    //if smallest element is first or last in its subarray
    return 0;
  }
  if (r - l == 1) {
    //for size one array there exists only one possible subarray
    //we also need to add the linear function
    return A[l] * A[l] + A[l] * (a * l + b);
  }
  //This is the call to your RMQ data structure
  int m = findMinIdxInSubArray(A, l, r);
  int result = 0;

  //to the left function would be (i + 1 - l) * A[m] * (r - m) which expands to
  //i * A[m] * (r - m) + (1 - l) * A[m] * (r - m)
  result += program(A, l, i, a + A[m] * (r - m), b + (1 - l) * A[m] * (r - m));
  
  //to the right function would be (r - i) * A[m] * (m - l + 1) wich expands to
  //i * -A[m] * (m - l + 1) + r * A[m] * (m - l + 1)
  result += program(A, m + 1, r, a - A[m] * (m - l + 1), b + r * A[m] * (m - l + 1));

  //This is the case for the element m itself,
  //as it is not accounted in the previous calculations
  //the linear function also needs to be accounted here
  result += A[m] * (m - l + 1) * (r - m) + A[m] * (a * m + b);
  return result;
}

现在，旧函数的编写方式如下：

public int program(int A[], int n) {
  //initialize your RMQ data structure here
  return program(A, 0, n, 0, 0);
}

请注意，此实现缺少findMinIdxInSubArray函数，正如我所提到的，这里可以使用任何RMQ数据结构。随意使用从Fenwick树到稀疏表的任何东西。

第一次调用函数时，它的子数组从0到4不等，现在不考虑任何元素。该子阵列的最小值为索引2处的元素1，因此m=2。

1是所有子阵列[i，j]的最小值，因此<代码>i

对于1右侧的元素4，它出现在3个数组中（[0,3]，[1,3]，[2,3]），并且将调用函数-3*i 12的递归调用。在这个函数调用中，它是大小为1的数组，因此我们将考虑子数组{4}和16，因为它是索引3，它的线性函数值-3 * 3 12 = 3，因此我们还将添加4*3=12来考虑第一个函数调用中的数组。

对于元素1本身，它出现在6个数组中（[0,2]、[0,3]、[1,2]、[1,3]、[2,2]和[2,3]），在上一个公式中，将按预期添加为1*3*2，对总和贡献6。

现在是左边较硬的数组。元素3恰好出现在2个这样的数组（[0,2]和[0,3]）中，并且贡献因子为2（2个数组乘以每个最小值1），元素2恰好出现在4个这样的数组中（[0,2]，[0,3]，[1,2]和[1,3]）。对于这两个元素，我们将调用一个线性函数为2*i 2的程序，正如人们所看到的，它与它们的贡献相匹配。

在这个递归调用中，我们会发现索引1处的2是最小的元素。在它的右侧，没有元素，因此递归调用将返回0。2本身出现在两个子数组（[0,1]和[1,1]）中，从它们中，它将贡献8（2个数组的总和值为2,2是最小值）到总和。但是线性函数提到我们还应该从之前的级别添加21 1=4个数组最小值，这与我们之前的计算与8的贡献相匹配。因此对于2，我们将在本次迭代中总共添加16个。

在这两个元素的左边，只有一个元素，它是三个元素，它只出现在一个数组中，因此它的贡献因子应该增加2（一个数组，但最小值是两个）。递归传递的函数将是（2*i 2）（2*i 2）=（4*i 4）。当我们处理一个元素3的子数组时，我们将从子数组{3}中加上9的贡献，再加上另一个3*（4*0 4），以说明之前级别上的数组，总贡献将是另一个21。

因此，递归函数将产生21 16 6 28=71的总和。现在让我们手动验证这个结果：

{3} - min=3, sum=3, min*sum=9
{3,2} - min=2, sum=5, min*sum=10
{3,2,1} - min=1, sum=6, min*sum=6
{3,2,1,4} - min=1, sum=10, min*sum=10
{2} - min=2, sum=2, min*sum=4
{2,1} - min=1, sum=3, min*sum=3
{2,1,4} - min=1, sum=7, min*sum=7
{1} - min=1, sum=1, min*sum=1
{1,4} - min=1, sum=5, min*sum=5
{4} - min=4, sum=4, min*sum=16

总计：9 10 6 10 4 3 7 1 5 16=71

编辑

如果使堆栈大小变大不可能使递归工作，那么以下是相同的想法，但不使用递归：

//This uses inclusive l and exclusive r
public int program(int[] A) {
  //for every possible l we would store all other call parameters
  //in the deepest call with this l
  int[] r = new int[A.length];
  int[] a = new int[A.length];
  int[] b = new int[A.length];
  r[0] = A.length;
  a[0] = 0;
  b[0] = 0;
  int result = 0;
  for (int l = 0; l < A.length; ++l) {
    //this loop would go down recursive calls to
    //the deepest call with the same l
    while (r[l] - l > 1) {
      int m = findMinIdxInSubArray(A, l, r[l]);

      //adding to center element
      r[m] = m + 1;
      //everything that was previously added to the result
      //should be stored in a and b
      a[m] = a[l];
      b[m] = b[l] + (m - l + 1) * (r - m);

      //right recursion step
      r[m + 1] = r[l];
      a[m + 1] = a[l] - A[m] * (m - l + 1);
      b[m + 1] = b[l] + r * A[m] * (m - l + 1);

      //left recursion step
      r[l] = m;
      a[l] = a[l] + A[m] * (r - m);
      b[l] = b[l] + (1 - l) * A[m] * (r - m)
    }
    result += A[l] * (a[l] * l + b[l]);
  }

Answer 2

您可以尝试使用递归。

int[] array = {1,2,3};
int maxSum = totalOfSubArray(array, 0, 0);

    private static int totalOfSubArray(int[] arr, int currentIndex, int maxSum) {
        int currentSum = 0;

        if (currentIndex == arr.length) {
            System.out.println("final total: " + maxSum);
            return maxSum;
        }

        String result = "";
        for (int i = currentIndex; i < arr.length; i++) {
            result += arr[i];
            currentSum += arr[i];
            int min = Math.min(arr[currentIndex], arr[i]);
            maxSum += min * currentSum;
            System.out.println("[" + result + "]  min : " + min + " currentSum: " + currentSum + " maxSum: " + maxSum);
        }

        return totalOfSubArray(arr, currentIndex + 1, maxSum);
    }

Answer 3

这个问题可以在时间和空间上解决。

该技术是对所有最近的较小值使用算法来找到最小元素为x的最大数组，对于所有元素x。这第一步以前作为单独的帖子被问过；这里的方法和解释部分借鉴了我那里的答案。

为了避免重复的问题，我们会说x是子数组的最小元素，当它是最左边的最小值时，即没有以前的元素像x一样小，也没有任何未来的元素严格小于x在其子数组中。

对所有最近的较小值使用算法，对于每个索引i0

现在，我们必须计算每个元素对总和的单独贡献。我们将把它分成两部分：最小值位于i或左侧的子数组的A[i]的贡献，以及最小值严格位于i之后的子数组的A[i]的贡献。

 1. For each position i in the array A, 
    let M = (m_0, m_1, ... m_r) be the indices of the 
    ordered sequence of (weak) minima we see, starting
    with m_0 = -1 and ending at m_r = i.

For example, if 
A = (5, 3, 9, 4, 6, 8, 10, 1, 2, 7)

then the sequence for A[5]==8 would be:
M = -1, 1, 3, 4, 5

corresponding to the minima 
-infinity, 3, 4, 6, 8

seen walking left from A[5]==8.

 2. Let C(m_j, i), 1 <= j <= r, be the count of 
    subarrays of A that have m_j as their minimum
    and contain A[i]. We can also let D(m_j, i) be
    this count of arrays times the shared minimum
    of the arrays: D(m_j, i) = A[m_j]*C(m_j, i).

 3. The contribution of A[i] to the total sum 
    from subarrays whose minimum is located 
    at or before i is the 
    sum over j, 1 <= j <= r, of D(m_j, i)*A[i].
    Note that this sum excludes the 
    fake minimum of -infinity

如果已经计算了next_smaller元素和previous_smaller_or_equal元素到i的索引，那么

C(i, i) = (next_smaller[i] - i) 
        * (i - previous_smaller_or_equal[i]).

到目前为止，我所描述的仍然是O（n^2）算法。诀窍是我们可以从C（m_j， i）计算C（m_j， i 1），并且我们不需要实际计算C的单个值对于之前的最小值；只有上面代码块（3）末尾提到的总和。

C(m_j, i+1) = C(m_j, i) - (m_j-m_{j-1}) 
                     if A[i+1] >= A[m_j], and

            = 0 
                     if A[i+1] < A[m_j].

这意味着我们的C函数的值以固定的线性速率减少，与i无关，直到我们达到一个严格小于a[m\u j]的数字，此时，m\u j的和贡献减少到零。

这表明当我们扫描A时，我们应该保持一个（弱）单调堆栈，存储我们从左到右看到的（弱）最小值以及它对我们的D（m_j， i）函数和减少的固定线性速率。在A[i]中，我们对我们的运行总和执行线性递减，从堆栈顶部弹出所有严格大于A[i]的元素（同时删除它们对运行总和减少的贡献），将A[i]*运行总和添加到我们的总数中，并将A[i]推送到堆栈顶部。

由于A的每个元素最多添加和从堆栈中删除一次，因此这在O（n）时间内运行。

A[i]对最小值严格位于i之后的子数组的总和的贡献完全类似于从右到左计算，除了我们保持严格的单调堆栈，并且不计算A[i]的贡献来自具有A[i]作为最小值的子数组；这些已经被计算在内。

这是Java中的完整代码。为了处理整数溢出（因为总和的单个项可以像max（A）**2*n或10**24一样大），我已经将所有算术转换为使用Bigintger。我不是Java专家，所以可能有更好的修复方法或使用开销更少的任意精度整数的方法。

import java.math.BigInteger;
import java.util.*;

public static int sub_sums(int[] A, int n) {
    /* Given an array of integers A, compute the
    sum over all subarrays B of min(B)*sum(B)
    by using nearest smaller values

    Run-time: O(n), and O(n) extra space
    */

    ArrayList<BigInteger> nums = new ArrayList<BigInteger>(n);
    for (int i = 0; i < n; i++){
        nums.add(BigInteger.valueOf(A[i]));
    }


    BigInteger big_n = BigInteger.valueOf(n);

    BigInteger MOD = BigInteger.valueOf(7 + 1000_000_000);

    var previous_smaller_or_equal = new int[n];
    var next_smaller = new int[n];

    for (int i = 0; i < n; i++) {
        previous_smaller_or_equal[i] = i;
        int j = i-1;
        while (j >= 0 && A[j] > A[i]){
            j = previous_smaller_or_equal[j];
        }
        previous_smaller_or_equal[i] = j;
    }

    for (int i = n-1; i >= 0; i--) {
        next_smaller[i] = i;
        int j = i+1;
        while (j < n && A[j] >= A[i]){
            j = next_smaller[j];
        }
        next_smaller[i] = j;
    }

    BigInteger total = BigInteger.ZERO;
    BigInteger running_sum = BigInteger.ZERO;
    BigInteger running_sum_decrease = BigInteger.ZERO;

    var s = new Stack<Integer>();

    for (int i = 0; i < n; i++) {

        // Contributions of this element as minimum
        BigInteger term_1 = BigInteger.valueOf(next_smaller[i] - i);
        BigInteger term_2 = BigInteger.valueOf(i - previous_smaller_or_equal[i]);

        running_sum = running_sum.add(nums.get(i).multiply(term_1).multiply(term_2));

        running_sum = running_sum.subtract(running_sum_decrease);

        while (!s.empty() && A[s.peek()] > A[i]){
            var last = s.pop();
            BigInteger term_3 = nums.get(last).multiply(BigInteger.valueOf(last- previous_smaller_or_equal[last]));
            running_sum_decrease = running_sum_decrease.subtract(term_3);
        }

        total = total.add(nums.get(i).multiply(running_sum));

        running_sum_decrease = running_sum_decrease.add(term_2.multiply(nums.get(i)));

        s.push(i);
    }

    s.clear();
    running_sum = BigInteger.ZERO;
    running_sum_decrease = BigInteger.ZERO;

    for (int i = n-1; i >= 0; i--) {

        running_sum = running_sum.subtract(running_sum_decrease);
        total = total.add(nums.get(i).multiply(running_sum));

        // Contributions of this element as minimum
        // Added afterwards now, since forward-pass already counted once

        BigInteger term_1 = BigInteger.valueOf(next_smaller[i] - i);
        BigInteger term_2 = BigInteger.valueOf(i - previous_smaller_or_equal[i]);

        running_sum = running_sum.add(nums.get(i).multiply(term_1).multiply(term_2));

        while (!s.empty() && A[s.peek()] >= A[i]){
            var last = s.pop();
            BigInteger term_3 = nums.get(last).multiply(BigInteger.valueOf(next_smaller[last]- last));
            running_sum_decrease = running_sum_decrease.subtract(term_3);
        }

        running_sum_decrease = running_sum_decrease.add(term_1.multiply(nums.get(i)));

        s.push(i);
    }

    return (total.mod(MOD)).intValue();
}

示例用法：

int[] d = {1, 2, 3};
System.out.println(sub_sums(d, 3));  // Returns 33
int[] c = {3, 2, 1, 4};
System.out.println(sub_sums(c, 4));  // Returns 71