Найдите максимум из всех минимальных сумм
Даны целочисленные массивы A и B размера n.
Найдите все возможные комбинации (подмножества) размера 1, 2, 3, ..., n. Мы получаем 2 степени n возможностей
Для каждой комбинации (подмножества) A найдите минимум в этом подмножестве, скажем min, и умножьте это значение на сумму элементов для этой комбинации из массива B.
Найдите максимальное значение из всех вышеуказанных минимумов. Верните результат по модулю (10^9+7).
Ограничения:
n in range 1 to 10^5
1 <= A[i], B[i] <= 10^6
Пример:
A = [1,1,3]
B = [1,2,2]
indices: A min B sum min*sum
(subset A) (subset B)
--------------------------------------------------------------
[0] 1 1 1 1 1*1=1
[1] 1 1 2 2 1*2=2
[2] 3 3 2 2 3*2=6
[0,1] 1,1 1 1,2 3 1*3=3
[0,2] 1,3 1 1,2 3 1*3=3
[1,2] 1,3 1 2,2 4 1*4=4
[0,1,2] 1,1,3 1 1,2,2 5 1*5=5
Result = max( all min*sum) = max(1,2,6,3,3,4,5) = 6
Вот мой код:
public static int solve(List<Integer> A, List<Integer> B) {
int n = A.size();
long max = 0;
final int MOD = 1_000_000_007;
// Loop through all subsets using bitmasking
for (int mask = 0; mask < (1 << n); mask++) {
int min = Integer.MAX_VALUE;
long sum = 0;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
min = Math.min(min, A.get(i));
sum += B.get(i);
sum %= MOD; // To prevent overflow
}
}
long current = (int) ((long) min * sum % MOD);
max = Math.max(max, current);
}
return (int) max;
}
Об этом спросили во время собеседования в рамках хакерранка, когда я использовал этот код, он прошел только 4 из 15 тестовых случаев. Многие из них потерпели неудачу из-за неправильного вывода и ошибок тайм-аута.
Каков правильный подход к решению этой проблемы?
Ответы 1
Вы можете попробовать все элементы в A как минимальное значение некоторой подпоследовательности A. Чтобы максимизировать произведение (min in A) * (sum in B) для фиксированного минимума, мы можем выбирать только элементы из B, чтобы добавить их к сумме, для которой элемент из A с соответствующим индексом не меньше этого фиксированного минимума. Кроме того, существует особый случай, когда элемент, соответствующий текущему элементу в A, который мы пытаемся использовать как минимум, всегда должен приниматься как минимум.
Затем мы можем выбрать оптимальные элементы, рассмотрев два случая (не пытаясь перепробовать все подмножества):
- Если рассматриваемый нами минимум положителен, то мы хотим взять как можно больше положительных соответствующих элементов из B.
- Если минимум отрицательный, то мы хотим взять в B как можно больше отрицательных элементов.
Обратите внимание, что случай минимума 0 может относиться к любому из случаев: произведение всегда будет 0.
Мы можем предварительно вычислить сумму всех положительных элементов в B с соответствующим элементом в A, превышающим определенное значение, с помощью префиксного массива сумм (после сортировки List индексов A в порядке убывания на основе значений в A). Мы можем сделать то же самое с отрицательными элементами.
Наконец, для каждого элемента мы можем выполнить двоичный поиск, чтобы найти его индекс в отсортированной версии A и использовать его для доступа к массивам сумм префиксов.
Временная сложность: O(N log N)
public static int solve(List<Integer> A, List<Integer> B) {
var sortedIndexesByA = IntStream.range(0, A.size()).boxed()
.sorted(Comparator.comparingInt(A::get).reversed()).toList();
long[] bSumPos = new long[B.size()], bSumNeg = new long[B.size()];
for (int i = 0; i < B.size(); i++) {
bSumPos[i] = (i > 0 ? bSumPos[i - 1] : 0) +
Math.max(B.get(sortedIndexesByA.get(i)), 0);
bSumNeg[i] = (i > 0 ? bSumNeg[i - 1] : 0) +
Math.min(B.get(sortedIndexesByA.get(i)), 0);
}
long ans = Long.MIN_VALUE;
for (int i = 0; i < A.size(); i++) {
int low = 0, high = A.size() - 1;
while (low <= high) {
int mid = low + high >>> 1;
if (A.get(sortedIndexesByA.get(mid)) < A.get(i))
high = mid - 1;
else
low = mid + 1;
}
long sum = (A.get(i) > 0 ? bSumPos : bSumNeg)[high] +
(A.get(i) > 0 ^ B.get(i) > 0 ? B.get(i) : 0);
ans = Math.max(ans, sum * A.get(i));
}
return (int) (ans % 1000000007);
}
@AndreyB.Panfilov sum — это long, и такие задачи почти никогда не требуют целочисленных типов размером более 64 бит.
сумма не переполняется, умножение переполняется
@AndreyB.Panfilov Я говорю, что, поскольку для решения задач обычно не требуются целочисленные типы размером более 64 бит, достаточно, чтобы умножение выполнялось как long.
Пожалуйста, просто рассмотрите два одинаковых набора: [5 из int.min_val]. Максимум будет: int.min_val x ((long) (int.min_val) x 5) — переполняется как int, так и long.
Я пытаюсь понять этот ответ шаг за шагом и застрял в операторе We can precompute the sum of all positive elements in B with corresponding element in A larger than a particular value with a prefix sum array и соответствующем коде bSumPos[i] = (i > 0 ? bSumPos[i - 1] : 0) + Math.max(B.get(sortedIndexesByA.get(i)), 0); не могли бы вы добавить больше деталей или пример, чтобы понять эту часть логики?
Кроме того, значения массива всегда положительны, поэтому нам нужно проверять наличие отрицательных значений.
@Sid Я сделал свой ответ более общим (обработка негативов), поскольку в вопросе не уточнялось. Короче говоря, bSumPos[i] хранит сумму всех положительных значений в B, где значение в A по тому же индексу больше или равно значению по индексу i в копии A с обратной сортировкой.
@AndreyB.Panfilov, для моей задачи подойдет длинный вариант, так как при вычислении значений я буду использовать модуль (10^9+7).
bSumPos[i] stores the sum of all positive values in B where the value in A at the same index is greater or equal to the value at index i in a reverse sorted copy of A. Я ничего не понимаю, не могли бы вы объяснить на примере, как это помогает в решении этой проблемы.
@Sid Допустим, мы пробуем какое-то значение x в A в качестве минимального значения. Тогда мы можем выбирать только другие элементы из A, которые больше или равны x, в качестве других элементов этого подмножества. Мы хотим выбирать только те элементы, которые увеличивают сумму в B, поэтому мы хотим брать только те элементы из A, у которых элемент в B имеет тот же индекс и имеет положительное значение. Вы это видите?
не уверен, предполагалось ли это в исходной загадке, однако
ans = Math.max(ans, sum * A.get(i))также страдает от целочисленного переполнения