Найдите максимально допустимое количество негативов

Учитывая массив положительных чисел размера n, выберите как можно больше элементов из этого массива и умножьте на -1, так чтобы совокупная сумма всегда была больше 0. Возвращает количество элементов, которые можно сделать отрицательными в результате.

Пример:

Тестовый пример 1: [5,3,1,2]

Результат = 2

Объяснение:

выберите индексы 1 и 2 и сделайте их отрицательными итак [5,-3,-1,2] совокупная сумма равна [5,2,1,3]

Есть и другие возможности, например [5,-3,1,-2]

Мой подход к кодированию такой:

static int solve(int[] arr) {
    long sum = 0;
    int result = 0;
    for(int e : arr) {
        int neg = -e;
        if (sum + neg >0) {
            result++;
            sum += neg;
        } else {
            sum += e;
        }
    }
    return result;
} 

Но мой подход неверен, поскольку в некоторых случаях он дает неверный результат, например:

arr = [5,2,3,5,2,3]

Expected output = 3, my code results = 2

possible solution is [5,-2,3,5,-2,-3]

Каков правильный подход к решению этой проблемы?

Есть ли у этой проблемы веб-страница? Если да, то было бы вежливо добавить ссылку.

Old Dog Programmer 08.04.2024 19:31

@OldDogProgrammer, у меня нет ссылки на эту проблему

Learner 08.04.2024 19:48

Я заметил, что многие ваши вопросы связаны с LeetCode и другими проблемами, например проблемами. Не хочу отговаривать вас от публикации сообщений на SO, но знаете ли вы, что существует обмен мнениями, посвященный этому типу программирования. Называется он Код Гольф. Подумал, что тебе это может понравиться.

WJS 08.04.2024 22:06

@WJS Соревновательное программирование и код-гольф — это не одно и то же. Очень редко методы решения пересекаются. Эффективность обычно полностью игнорируется при решении задач по кодированию гольфа.

Unmitigated 08.04.2024 22:07

@Unmitigated Ну, когда я прочитал некоторые задачи на Code Golf, они наверняка напоминали многие, которые я видел на сайтах соревновательного программирования.

WJS 08.04.2024 22:09

@WJS Я не хотел подразумевать иное, но проблемы с кодовым гольфом часто решаются грубой силой, поскольку правила требуют только решений для теоретического решения проблемы в конечном итоге. Вопросы по алгоритмам лучше задавать здесь.

Unmitigated 08.04.2024 22:11

Спасибо за ответ. Поскольку для этих задач нам недоступны страницы, для решения будущих проблем может оказаться полезным, если вы поделитесь ограничениями и ожиданиями.

Old Dog Programmer 09.04.2024 16:19
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
0
7
397
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вы всегда можете попытаться инвертировать текущий элемент, если это возможно, отслеживая при этом элементы, удаленные на данный момент в очереди мультимножества или приоритетной очереди. Если текущий элемент невозможно удалить из суммы, попробуйте заменить его наибольшим ранее удаленным элементом, если последний больше.

static int solve(int[] arr) {
    long sum = 0;
    int result = 0;
    var removed = new PriorityQueue<Integer>(Collections.reverseOrder());
    for (int x : arr) {
        if (sum - x > 0) {
            sum -= x;
            removed.add(x);
            ++result;
        } else if (!removed.isEmpty() && removed.peek() > x) {
            sum += removed.poll() - x;
            removed.add(x);
        } else sum += x;
    }
    return result;
}

Спасибо, я пытаюсь это понять. sum += removed.lastKey() - x; здесь мы все еще уменьшаем на x правильно, тогда removed.merge(x, -1, Integer::sum) почему мы уменьшаем его частоту на карте, а не увеличиваем ее.

Learner 09.04.2024 00:10

@learner Это опечатка. Я исправил метод.

Unmitigated 09.04.2024 00:16

Прав ли я, полагая, что временная сложность этого алгоритма составляет O(N log N)? Я думал о попытке грубого решения, которое было бы экспоненциальным.

k314159 09.04.2024 09:52

@ k314159 k314159 Да, это O(N log N).

Unmitigated 09.04.2024 13:56

Другие вопросы по теме

Эффективно подсчитать количество равносторонних и равнобедренных треугольников, которые можно построить из набора точек
Транспортная задача и метод ветвей и границ
Логика, которую нужно реализовать, чтобы получить максимальное количество очков
Что происходит с потерянной частью односвязного списка, когда я добавляю цикл в середине?
Эффективный способ найти сумму наибольших элементов x в подмассиве
Инициализируйте двумерный массив значениями, указанными в таблице ниже
Как я могу придумать алгоритм для разделения ряда чисел в заданном соотношении, чтобы округленные разделения складывались в исходное число?
Рекурсивное построение древовидной структуры данных из массива строк, сохраняющих порядок приоритета
Алгоритм разделения целого числа на группы определенных меньших целых чисел
Изменение масштаба массива в JavaScript или Python до определенного максимального значения и целевой суммы