Найти сумму максимальных подмассивов
Об этом спросили в ОА. Дан массив натуральных чисел размера n.
Для каждого элемента массива (индексы от 0 до n - 1) найдите размер наибольшего подмассива, содержащего текущий элемент, такой, что текущий элемент равен максимальному элементу в этом подмассиве, и добавьте этот размер к результату (который начинается в 0).
Пример:
arr = [3,5,6]
Result = 6
Объяснение:
i=0 => [3] = max subarray with 3 as maximum, size of sub-array is 1
i=1 => [3,5] = max subarray with 5 as maximum, size of sub-array is 2
i=2 => [3,5,6] = max subarray with 6 as maximum, size of sub-array is 3
Sum = 1 + 2 + 3 = 6
Пример:
arr = [ 1,2,1]
Result = 5
Объяснение:
i = 0 => [1] max subarray, size = 1
i = 1 => [1, 2, 1] max subarray with 2 as maximum, size = 3
i = 2 => [1], max subarray with 1 as maximum, size = 1
Result = 1 + 3 + 1 = 5
Пример:
arr = [1,1,1,1]
Result = 16
Объяснение:
i = 0 => [1, 1, 1, 1] max subarray with 1 as maximum, size = 4
Same for i=1, 2, 3 => max subarray for each case is still [1,1,1,1] with size 4
Result = 4 + 4 + 4 + 4 = 16
Вот мой код:
public class Main {
public static int solve(int[] arr) {
int n = arr.length;
int result = 0;
int currentMax = Integer.MIN_VALUE;
int size = 0;
for (int i = 0; i < n; i++) {
currentMax = Math.max(currentMax, arr[i]);
if (arr[i] == currentMax) {
size++;
int backUp = size;
for(int j=i+1; j<n; j++) {
if (arr[j] <= currentMax) {
size++;
} else {
break;
}
}
result += size;
size = backUp;
} else {
size = 1;
currentMax = arr[i];
result++;
}
}
return result;
}
public static void main(String[] args) {
System.out.println(solve(new int[]{3,5,6}));//6
System.out.println(solve(new int[]{1,2,1}));//5
System.out.println(solve(new int[]{1,1,1,1}));//16
}
}
Мой код работал только для примеров тестовых случаев и не работал для остальных случаев, которые скрыты, поэтому я не могу их увидеть. Каков правильный подход к решению этой проблемы? Тестовые примеры не показали неправильный результат, ошибок тайм-аута нет.
Самые большие подмассивы [6,5,3], [5,3], [3], поэтому результат 3+2+1=6
но является ли это фактическим результатом? («правильный подход», которому я бы следовал, — это найти случай, дающий неправильные результаты)
@user85421 user85421, да, это должно быть правильно, но у меня нет работающего сайта, чтобы проверить это.
Итак: ideone.com/Nuulcw -- следующий шаг: отладка (думаю, вся идея с currentMax не работает; но я действительно не понял алгоритм)
@user85421 user85421, понятно, чтобы исправить это, мне нужно добавить еще один цикл for внутри блока else, но это увеличит временную сложность.
@SupportUkraine Да, похоже, это опечатка.
Ответы 1
По сути, эта проблема требует поиска ближайшего большего элемента с обеих сторон для каждого элемента массива. Это можно сделать за O(n) с помощью монотонного стека.
public static long solve(int[] arr) {
var dq = new ArrayDeque<Integer>(arr.length);
int[] prevLarger = new int[arr.length], nextLarger = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
while (!dq.isEmpty() && arr[dq.peek()] <= arr[i]) dq.pop();
prevLarger[i] = dq.isEmpty() ? -1 : dq.peek();
dq.push(i);
}
dq.clear();
for (int i = arr.length - 1; i >= 0; i--) {
while (!dq.isEmpty() && arr[dq.peek()] <= arr[i]) dq.pop();
nextLarger[i] = dq.isEmpty() ? arr.length : dq.peek();
dq.push(i);
}
long ans = 0;
for (int i = 0; i < arr.length; i++) ans += nextLarger[i] - prevLarger[i] - 1;
return ans;
}
какой ожидаемый результат
[6, 5, 3]? (1-й пример наоборот)