UniLecs #138_1. Максимальная последовательность по модулю
UniLecsЗадача: есть массив целых чисел. В нем необходимо определить подмножество с максимальным модулем суммы чисел входящих в него.
Входные данные: arr - массив целых чисел, размер массива от 1 до 10^4.
Вывод: подмножество чисел исходного массива, ктр образуют множество с максмимальным модулем суммы. Если есть несколько множеств с одинаковым модулем суммы, то выводите любое.
Пример: [-1, 2, -1, 3, -4]
Answer: { -1, -1, -4 }
Реализация:
- Andrew Bystrov, Java: 1 балл
https://gist.github.com/AndrewBystrov/cfe3e784b7c66fdc81b4e22b3ed6a50c
2. @mrmeison, JS: 1 балл
http://jsfiddle.net/hvrmqy45/5/
3. @akolosov364, JS: 1 балл
Создается два массива, в один добавляются все положительные, в другой - все отрицательные. Если сумма всех элементов массива положительная то стоит вернуть положительный массив.
https://gist.github.com/KolosovAO/b2230e888ed72e6e56013a8065788aa4
4. @LostInKadath, Lisp, C++: (1 + 0.5 балла за доп.метод + 0.1 балл за доп.модификацию алгоритма + 0.1 балла за доп.ЯП) = 1.7 балла
https://gist.github.com/LostInKadath/e2ba4ee0644fe2eda8a01c410735827a
5. @jinxonik, Ruby, C++, Python: (1 + 0.5 за доп.метод + 2*0.1 за 2 доп.модификации алгоритма + 2*0.1 за 2 доп.ЯП) = 1.9 балла
https://gist.github.com/jin-x/0a0605b757b02f5d657e3fa9a0406a59
Test Ruby: https://repl.it/@jin_x/UniLecs-138-maxabssumrb
Test C++: https://repl.it/@jin_x/UniLecs-138-maxabssumcpp
Test Python: https://repl.it/@jin_x/UniLecs-138-maxabssumpy
6. @egormasharskii, С++: 1.5 балла за 2 разных подхода в решении
https://gist.github.com/unilecs/17a83ca62b843de56f7e4178fe57740a
7. @kirillmotrichkin, Python: (1 + 2*0.5) = 2 балла
Метод 1: Ответом будет либо все положительные числа массива, либо все отрицательные (доказывается от противного, иначе всегда можно улучшить модуль суммы). Первое решение: пройдём по массиву, поделим массив на подмножество отрицаительных и положительных и сравним их модули сумм.
https://gist.github.com/superkiria/f066d5ffd6a4bd39fab1c02979084e84
Test: https://repl.it/@superkiria/unilecs138-1
Метод 2: Второе решение без циклов, но самое медленное. Отсортируем массив, возьмём отрицательную часть (она будет слева от нуля), сравним с положительной (она будет справа) и вернём одну из них.
https://gist.github.com/superkiria/4242ab2af722d4277c326ac573a21fc4
Test: https://repl.it/@superkiria/unilecs138-2
Метод 3: Третье решение самое быстрое и простое. Посчитаем сумму всего массива, если она положительна, то ответ - все положительные числа, иначе - отрицательные. Пройдём по массиву, собирая только нужные числа.
https://gist.github.com/superkiria/66b0a75618f209f4abc36858cc3e760e
Test: https://repl.it/@superkiria/unilecs138-3
8. @FutorioFranklin, Python: 1 балл
https://gist.github.com/futorio/e34766e83913ef6937c87496b39345b1
9. Антон, Python, Haskell, Rust: (1 + 0.5 балла + 0.1 за доп.модификацию алгоритма в Rust + 0.5 балла за вариант с брутфорсом в Python + 2*0.1 за 2 доп.ЯП) = 2.3 балла
Rust: https://gist.github.com/AnthonyMikh/fccff6b3fa430f460ed12703863f93da
Haskell: https://gist.github.com/AnthonyMikh/5efd3f5c6d4445dc8f1062931c0657f3
Python: https://gist.github.com/AnthonyMikh/1457d0870665041d05f37a1cf74afdfe
10. @Darttur, Java, Python: 1.1 балла
Java: https://repl.it/@darttur/task138JAVA
Python: https://repl.it/@darttur/task138PYTHON
11. @Loskir, C++, JS, Python: (1 + 0.5 балла за доп.решение + 2*0.1 за 2 доп.ЯП) = 1.7 балла
https://gist.github.com/Loskir/580b1fec1dec3b8cd7a5092101e8bb47
Test C++: https://repl.it/@Loskir/UniLecs138cpp
Test JS: https://repl.it/@Loskir/UniLecs138js
Test Python: https://repl.it/@Loskir/UniLecs138py
12. @matantsev01, С++: 1 балл
https://gist.github.com/e-maks/0e4d3c6ead1329847cd117e1fad5f071
Test: https://repl.it/@emaks/BrilliantSuspiciousExabyte
13. @kupp1, Python: 1 балл
https://gist.github.com/kupp1/d817fa800a3ee77bf45a6a755cff80f1
14. @rustem_b, Python, Hy, Perl 6, Ruby, Julia, JavaScript: (1 + 5*0.1) = 1.5 балла
https://gist.github.com/RustemB/2de0792c28eb98e48259b2fc64880c35
15. @lPestl, C++, C#, F#: (1 + 2*0.5 + 2*0.1) = 2.2 балла
Метод 1. Простые суммы: Возвращает подмассив с максимальной суммой по модулю.
Метод 2. Сумма - индикатор: Получаем сумму для всего массива, если общая сумма - положительна, то и конечный подмассив надо строить из положительных элементов. Аналочино - если сумма отрицательна
Метод 3. Неоптимальный: Заведем вектор для сумм и в векторе для каждой суммы будем собирать свой подмассив.
C++: https://gist.github.com/lpestl/6bf48264d8218a2a803da887561ae5e4
C#: https://gist.github.com/lpestl/ac041fae9aa937dac12f158c38855b50
F#: https://gist.github.com/lpestl/355c3f561ae66ecc1f55109d53b7f7ff
16. @voodoo_woodpecker, Python, JS, R: (1 + 2*0.1 балла за доп.модификации алгоритма + 2*0.1 балла за 2 доп.ЯП) = 1.4 балла
Подробный разбор:
https://telegra.ph/UniLecs138-i-nebolshie-zametki-o-massivah-11-12