我有一个数字数组，现在我必须通过生成给定数组的所有可能的子数组并应用一些条件来查找元素之和。
\n条件是对每个子数组获取minimum并在其中找到total of elements并将两者相乘(minimum * total)。最后，add所有子数组的所有这些相乘值。
这是问题陈述：
\n使用以下公式查找所有可能子数组的总和：
\n\n\nSum(left, right) = (min of arr[i]) * (\xe2\x88\x91 arr[i])，其中 i 的范围从左到右。
\n
例子：
\nArray = [2,3,2,1]\n子数组是：[start_index, end_index]
\n [0,0] subarray = [2], min is 2 and total of items = 2. min * total = 2*2=4\n [0,1] subarray = [2,3], min is 2 and total of items = 5. min * total = 2*5=10\n [0,2] subarray = [2,3,2], min is 2 and total of items = 7. min * total = 2*7=14\n [0,3] subarray = [2,3,2,1], min is 1 and total of items = 8. min * total = 1*8=8\n\n [1,1] subarray = [3], min is 3 and total of items = 3. min * total = 3*3 = 9\n [1,2] subarray = [3,2], min is 2 and total of items = 5. min * total = 2*5 = 10\n [1,3] subarray = [3,2,1], min is 1 and total of items = 6. min * total = 1*6 = 6\n\n [2,2] subarray = [2], min is 2 and total of items = 2. min * total = 2*2 = 4\n [2,3] subarray = [2,1], min is 1 and total of items = 3. min * total = 1*3 = 3\n\n [3,3] subarray = [1], min is 1 and total of items = 1. min * total = 1*1 = 1\n \n Total = 4 + 10 + 14 + 8 + 9 + 10+ 6 + 4 + 3 + 1 = 69\n \n所以本例中的答案是 69。
\n限制条件：
\nEach array element is in range 1 to 10^9. Array size 1 to 10^5. Return response in modulo 10^9+7\n这是我尝试过的代码。
\npublic static int process(List<Integer> list) {\n int n = list.size();\n int mod = 7 + 1000_000_000;\n long result = 0;\n for (int i = 0; i < n; i++) {\n long total = 0;\n int min = list.get(i);\n for (int j = i; j < n; j++) {\n int p = list.get(j);\n total = (total + p) % mod;\n min = Math.min(min, p);\n result = (result + (min * total) % mod) % mod;\n }\n }\n return (int) result;\n}\n我想降低这个算法的时间复杂度？
\n解决此任务的更好方法是什么？
\n更新：
\nDavid Eisenstat已经给出了一个很好的答案，但我发现它很难理解并提供一个Java程序，有人可以为该方法提供一个java解决方案或提供一个伪代码，以便我可以想出一个程序。
Dav*_*tat 14
正如 user1984 所观察到的，我们无法o(n\xc2\xb2)通过对每个子数组进行持续的工作来实现这一目标。这是我们如何到达O(n).
子数组最小值是最难处理的因素，因此我们将其排除在外。假设元素成对不同，以避免在下面的数学中重复计算（代码不会改变）。让A范围超过子数组并且x元素，
sum_{A} [(sum_{y in A} y) (min A)] =\nsum_{x} [x sum_{A such that min(A) = x} (sum_{y in A} y)].\n首先关注一下sum_{A | min(A) = x} (sum_{y in A} y)，图片是我们有一个像这样的子数组
a b x c d e\n其中左侧的元素a（如果存在）小于x，右侧的元素e（如果存在）小于x，并且显示的所有元素都大于x。我们想要对包含 的所有子子数组求和x。
a b x\nb x\nx\na b x c\nb x c\nx c\na b x c d\nb x c d\nx c d\na b x c d e\nb x c d e\nx c d e\n我们仍然没有时间对这些子子数组求和，但幸运的是有一个模式。以下是每个元素出现在子子数组中的次数。
\na: 4 = 1 * 4 appearances\nb: 8 = 2 * 4 appearances\nx: 12 = 3 * 4 appearances\nc: 9 = 3 * 3 appearances\nd: 6 = 3 * 2 appearances\ne: 3 = 3 * 1 appearances\n这一见解将一个子数组的处理时间减少到O(n)，但仍然存在n子数组，因此我们还需要两个想法。
现在是弄清楚子数组是什么样子的最佳时机。第一个子数组是整个数组。我们在最小元素处分割这个数组，并分别递归地研究左子数组和右子数组。
\n这种递归结构由标记二叉树捕获，其中
\n这称为treap，它可以通过与优先级解析类似的算法在线性时间内构造。[3,1,4,5,9,2,6]例如，对于数组，请参见下文。
1\n / \\\n3 2\n / \\\n 4 6\n \\\n 5\n \\\n 9\n最后一部分是能够聚合上面的总和模式。具体来说，我们想要实现一个在 C++ 中可能如下所示的 API：
\nclass ArraySummary {\npublic:\n // Constructs an object with underlying array [x].\n ArraySummary(int x);\n\n // Returns an object representing the concatenation of the underlying arrays.\n ArraySummary Concatenate(ArraySummary that);\n\n // Returns the sum over i of (i+1)*array[i].\n int WeirdSum();\n};\n这个接口的要点是我们实际上不需要存储整个数组来实现WeirdSum()。如果我们存储
length底层数组的长度，sum底层数组的通常总和，weird_sum底层数组的奇怪总和；那么我们可以将构造函数实现为
\nlength = 1;\nsum = x;\nweird_sum = x;\n并Concatenate()作为
length = length1 + length2;\nsum = sum1 + sum2;\nweird_sum = weird_sum1 + weird_sum2 + length1 * sum2;\n我们需要其中两个，每个方向一个。那么就只是深度优先遍历（实际上如果实现优先级解析的话，就是自下而上）。
\n您当前的解决方案具有时间复杂度O(n^2)（假设为list.get）O(1)。确实存在1 + 2 + ... + n-1 + n可以表示为 的运算n * (n + 1)/2，因此O(n^2)。
n * (n + 1)/2 有趣的是，您可以从 length 数组中获取子数组的数量n，如您的问题中所定义的，并且从您的代码中可以看出。
这意味着您正在对每个子数组执行一次操作，这是此任务所需的最少操作，因为您需要对每个子数组至少查看一次。
我的结论是，不可能降低此任务的时间复杂度，除非有一些数学公式可以帮助做到这一点。
这并不一定意味着没有方法可以优化代码，但这需要测试并且可能是特定于语言的。无论如何，它不会改变输入数组长度的n时间复杂度。n
感谢对我的逻辑的任何输入。我正在学习自己。