查找数组的所有可能的子数组并对它们求和

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_000_000。数组大小从 1 到 100_000。返回输出为模块 7+1000_000_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) 内解决。

基本思路

在这个解释中，可能潜入了很多相差一的错误，但这对于这个想法来说并不重要。令 m 为数组的最小值。那么任何包含 m 的子数组都将 m 作为最小值，并且所有其他子数组将完全在 m 之前或完全在 m 之后。让n为数组中元素的数量，并让我们将其视为m索引。然后，对于每个i < m子数组，我们计算包含第 i 个元素且至少具有第 m 个元素的子数组。正是如此i * (n - m)，因为在 i 之前有 i 个可能的左边缘，在 m 之后有 (n - m) 个可能的边缘。每个这样的数组都将 A[m] 作为最小值，并且每个元素i < m都会以 因子对所得总和做出贡献i * A[m] * (n - m)。因为i > m通过类似的推理，我们会得到(n - i) * A[m] * m。然后我们会递归地更新 m 之前和 m 之后的数组，然后循环得到结果。

问题出在更新中。将这些添加i * A[m] * (n - m)到所有可能的情况中，我将得到二次解。但正如人们所注意到的，两边都是关于 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 数据结构。随意使用从芬威克树到稀疏表的任何东西。

示例 为了更好地解释这个公式，我将跟踪该程序对数组的执行情况A={3,2,1,4}

首次调用该函数时，它具有从 0（含）到 4（不含）的子数组，并且现在不考虑任何元素。该子数组的最小值是索引 2 处的元素 1，因此 m=2。

1 是所有子数组 [i,j] 的最小值，使得i <= 2和2 <= j。

对于 1 右侧的元素 4，它出现在 3 个数组中（[0,3]、[1,3]、[2,3]），并且将调用函数 -3 * i + 12 的递归调用。在此函数调用中，它是大小为 1 的数组，因此我们将使用 16 来计算子数组{4}，并且由于它的索引为 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 为最小值）至总和。但线性函数提到我们还应该从之前的级别添加 2 1+1=4 数组最小值，这与我们之前的计算与贡献 8 相匹配。因此，对于 2，我们将在本次迭代中总共添加 16。

两者的左边只有一个元素，是三个，它只出现在一个数组中，所以它的贡献因子应该增加2（一个数组，但最小是2）。递归传递的函数将是(2*i+2) + (2*i+2) = (4*i+4). 当我们处理一个元素 3 的子数组时，我们会添加子数组中的 9 的贡献{3}和另一个 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

编辑

如果增大堆栈大小不可能使递归起作用，这里有相同的想法，但不使用递归：

{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