Вычислить все возможные суммы в массиве из его подмассивов ⇐ JAVA

[Anonymous]

У меня есть массив чисел, теперь мне нужно найти сумму элементов, сгенерировав все возможные подмассивы данного массива и применив некоторые условия.
Условие указано для каждого подмассива получить минимум, а также найти в нем общее количество элементов и умножить оба (минимум * итог). Наконец, добавьте все эти умноженные значения для всех подмассивов.
Вот постановка задачи:
Найдите сумму всех возможных подмассивов, используя следующую формулу:

Sum(left, right) = (min of arr) * (∑ arr), где 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 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-решение для этого подхода или предоставить псевдокод, чтобы я мог придумать программу. п>

Подробнее здесь: https://stackoverflow.com/questions/708 ... sub-arrays