从子数组计算数组中所有可能的和

Question

我有一个数字数组，现在我必须通过生成给定数组的所有可能子数组并应用一些条件来找到元素之和。

条件是，对于每个子阵列，获取最小值，并找到其中的元素总数，然后将两者相乘（最小值*总数）。最后，将所有子阵列的所有这些相乘值相加。

以下是问题陈述：

使用下面的公式找到所有可能的子数组的总和：

和（左，右）=（最小的arr[i]) * (∑ arr[i]），其中i的范围从左到右。

例子：

Array = [2,3,2,1]

子数组是：[start_index，end_index]

 [0,0] subarray = [2], min is 2 and total of items = 2. min * total = 2*2=4
 [0,1] subarray = [2,3], min is 2 and total of items = 5. min * total = 2*5=10
 [0,2] subarray = [2,3,2], min is 2 and total of items = 7. min * total = 2*7=14
 [0,3] subarray = [2,3,2,1], min is 1 and total of items = 8. min * total = 1*8=8

 [1,1] subarray = [3], min is 3 and total of items = 3. min * total = 3*3 = 9
 [1,2] subarray = [3,2], min is 2 and total of items = 5. min * total = 2*5 = 10
 [1,3] subarray = [3,2,1], min is 1 and total of items = 6. min * total = 1*6 = 6

 [2,2] subarray = [2], min is 2 and total of items = 2. min * total = 2*2 = 4
 [2,3] subarray = [2,1], min is 1 and total of items = 3. min * total = 1*3 = 3

 [3,3] subarray = [1], min is 1 and total of items = 1. min * total = 1*1 = 1
 
 Total = 4 + 10 + 14 + 8 + 9 + 10+ 6 + 4 + 3 + 1 = 69
 

所以在这种情况下，答案是69。

约束：

Each array element is in range 1 to 10^9. Array size 1 to 10^5. Return response in modulo 10^9+7

这是我尝试的代码。

public static int process(List<Integer> list) {
    int n = list.size();
    int mod = 7 + 1000_000_000;
    long result = 0;
    for (int i = 0; i < n; i++) {
        long total = 0;
        int min = list.get(i);
        for (int j = i; j < n; j++) {
            int p = list.get(j);
            total = (total + p) % mod;
            min = Math.min(min, p);
            result = (result + (min * total) % mod) % mod;
        }
    }
    return (int) result;
}

我想降低这个算法的时间复杂度？

有什么更好的方法来解决这个任务？

更新：

David Eisenstat给出了一个很好的答案，但我发现很难理解，并附带了一个Java程序，有人可以为该方法提供java解决方案或提供伪代码，以便我可以想出一个程序。

Answer 1

David Eisenstat提供的答案非常有效，复杂性为O（n）。

我想分享另一种方法，虽然它的时间复杂度为O（n^2），但它可能更简单，并且可能更容易让一些人（包括我）完全理解。

1. 启动大小为矩阵[n][n]的二维数组，每个单元格将保存一对整数

for i in [0, n-1]:
    Matrix[i][i] = <arr[i], arr[i]>

for i in [0, n-1]:
   for j in[i, n-1]:
        Matrix[i, j] = < 
            Matrix[i - 1, j].sum + arr[i, j], 
            Min(Matrix[i - 1, j].min, arr[i, j]) 
        >

result = 0
for i in [0, n-1]:
   for j in[i, n-1]:
       result += Matrix[i, j].sum * Matrix[i, j].min

>

步骤2：在这里，我们从0迭代到n-1迭代，每次迭代都做恒定的功，因此时间复杂度为O（n）

步骤3：在这里，我们迭代了一半的矩阵单元（都在对角线的右边），每次迭代都做常数功，因此时间复杂度是<代码>O（（n-1）（n-2）。。。。（1） （0））=O（n^2）

第4步：与第3步类似的分析，O（n^2）

总共我们得到O（n^2）

这是动态编程方法的简单示例。

让我们将sub[i， j]定义为索引i和j之间的子数组，而0=

然后：

• 矩阵[i， j]. sum=子[i， j]中的和x
• 矩阵[i， j]. min=子[i， j]中的min x

为什么？

对于sub[i， i]很明显：

• sub[i，i]中的x之和=arr[i]

就像我们在步骤2中计算一样。

说服自己：

• <代码>sum sub[i，j]=sum sub[i-1，j]arr[i，j]

这解释了步骤3。

在步骤4中，我们只是总结所有内容，以获得所需的结果。

Answer 2

当前解决方案的时间复杂度为O（n^2），假设列表为。get是O（1）。确切地说有12个。。。n-1 n操作，可以表示为n*（n 1）/2，因此是O（n^2）。

有趣的是，n*（n 1）/2是您可以从长度n的数组中获得的子数组的数量，如您的问题中定义的并且从您的代码中可以明显看出。

这意味着您正在对每个子数组执行一个操作，这是此任务所需的最小操作，因为您需要至少查看每个子数组一次。

我的结论是，不可能降低这项任务的时间复杂度，除非有一些数学公式可以帮助做到这一点。

这并不一定意味着没有优化代码的方法，但这需要测试并且可能是特定于语言的。无论如何，它不会改变n方面的时间复杂度，其中n是输入数组的长度。

感谢您对我的逻辑提出的任何意见。我在学习自己。

Answer 3

正如user1984所观察到的那样，我们无法通过对每个子数组进行不断的工作来实现o（n²）。下面是我们如何获得O（n）的方法。

子数组最小值是最难处理的因素，所以我们将其计算出来。假设元素成对不同，以避免在下面的数学中重复计算（代码不会更改）。让A在子数组上移动，x在元素上移动，

sum_{A} [(sum_{y in A} y) (min A)] =
sum_{x} [x sum_{A such that min(A) = x} (sum_{y in A} y)].

首先关注sum{A | min（A）=x}（sum{y in A}y）我们有一个子数组，如

a b x c d e

如果a（如果存在）左侧的元素小于x，e（如果存在）右侧的元素小于x，并且显示的所有元素都大于x。我们要对包含x的所有子数组求和。

a b x
b x
x
a b x c
b x c
x c
a b x c d
b x c d
x c d
a b x c d e
b x c d e
x c d e

我们仍然没有时间对这些子子数组求和，但幸运的是有一个模式。这是每个元素出现在子子数组中的次数。

a: 4 = 1 * 4 appearances
b: 8 = 2 * 4 appearances
x: 12 = 3 * 4 appearances
c: 9 = 3 * 3 appearances
d: 6 = 3 * 2 appearances
e: 3 = 3 * 1 appearances

这一见解将一个子数组的处理时间减少到了O（n），但仍有n个子数组，因此我们还需要两个想法。

现在是时候弄清楚子数组是什么样子了。第一个子数组是整个数组。我们在最小元素处拆分这个数组，并分别递归地研究左边的子数组和右边的子数组。

这种递归结构被标记的二叉树捕获，其中

• 按顺序遍历是按顺序排列的数组元素；
• 每个节点都有一个小于其子节点的标签。（我仍然假设不同的元素。在实践中，我们可以做的是将数组索引声明为决胜局。）

这称为treap，它可以通过与优先级解析具有家族相似性的算法在线性时间内构建。例如，对于数组[3,1,4,5,9,2,6]，请参见下面。

  1
 / \
3   2
   / \
  4   6
   \
    5
     \
      9

最后一部分是能够聚合上面的总和模式。具体来说，我们希望实现一个在C中看起来像这样的API：

class ArraySummary {
public:
  // Constructs an object with underlying array [x].
  ArraySummary(int x);

  // Returns an object representing the concatenation of the underlying arrays.
  ArraySummary Concatenate(ArraySummary that);

  // Returns the sum over i of (i+1)*array[i].
  int WeirdSum();
};

这个接口的要点是，我们实际上不需要存储整个数组来实现WeirdSum（）。如果我们存储

• 底层数组的长度长度，
• 底层数组的通常和sum，
• 底层数组的奇怪总和weird_sum；

然后我们可以将构造函数实现为

length = 1;
sum = x;
weird_sum = x;

和Concatenate（）as

length = length1 + length2;
sum = sum1 + sum2;
weird_sum = weird_sum1 + weird_sum2 + length1 * sum2;

我们需要其中两个，每个方向一个。然后它只是深度优先遍历（实际上，如果您实现优先级解析，它只是自下而上）。