Йо, меня зовут Наби. Заранее благодарю за чтение и желаю продуктивно провести время! Если после прочтения возникнут вопросы, пожелания или предложения, то буду рад ознакомиться со всем в комментариях!
Предисловие:
В предыдущей части мы научились находить уникальный элемент в большом массиве, столкнулись с задачей одновременному отбору данных из двух массивов с определенным условием, обрабатывать строки так чтобы в итоге получить лишь уникальные значения, декодировать Азбуку Морзе и также обрабатывать определенные строки в предложении по заданному условию.
В этой части вас ждут еще более интересные алгоритмические задачи!
Перед началом чтения решения задачи, хочу призвать каждого к самостоятельному решению задачи, чтобы после вы могли сравнить своё решение с моим и обсудить это в комментариях. Буду рад послушать ваше мнение! Давайте, приступим!
Новое в конфигурации Algo1C (Последние 5 версий):
Актуальную версию конфигурации вы можете загрузить здесь (Нажмите на строку)
- 0.5 : Добавлена возможность выбирать контекст исполнения кода, например: НаСервере или НаКлиенте
- 0.4 : Исправлена ошибка при выводе содержимого исключения
- 0.3 : Добавлена возможность сохранять и загружать задачи; Внесены небольшие изменения в интерфейс
- 0.2 : Исправлена ошибка при выводе результата (Отдельная благодарность SAShikutkin)
Решение задач:
Задача 1
Платформа: CodeWars
Название задачи: Maximum subarray sum
Ссылка на задачу: https://www.codewars.com/kata/54521e9ec8e60bc4de000d6c (Нажмите на строку)
Сложность: 5 kyu
Тэги: Алгоритмы, Списки, Динамическое программирование, Фундаментальные, Производительность
Оригинальное описание задачи:
The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:
max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4])
# should be 6: [4, -1, 2, 1]
Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.
Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.
Пояснение:
От нас требуется в данном нам массиве, найти последовательность чисел с наибольшей суммой и затем вернуть эту сумму. Например в примере из оригинала, самую большую сумму образует последовательность чисел от 3(индекс) по 6(индекс). Давайте придумаем решение!
Решение:
В первую очередь, само собой, нам необходимо перебрать все элементы исходного массива. Максимальную и текущую сумму будем записывать в заранее объявленные переменные. Далее с каждой итерацией прибавляем к текущей сумме текущее число. Затем проверяем не ушла ли текущая сумма в минус, если ушла то обнуляем. Если всё нормально. проверяем больше ли текущее число чем максимальное число и, если так оно и есть, обновляем максимальную сумму. Опишем это кодом:
ИсходныйМассив = Новый Массив;
ИсходныйМассив.Добавить(-2);
ИсходныйМассив.Добавить(1);
ИсходныйМассив.Добавить(-3);
ИсходныйМассив.Добавить(4);
ИсходныйМассив.Добавить(-1);
ИсходныйМассив.Добавить(2);
ИсходныйМассив.Добавить(1);
ИсходныйМассив.Добавить(-5);
ИсходныйМассив.Добавить(4);
//
МаксимальнаяСумма = 0;
ТекущаяСумма = 0;
Для Каждого Стр Из ИсходныйМассив Цикл
ТекущаяСумма = ТекущаяСумма + Стр;
Если ТекущаяСумма < 0 Тогда
ТекущаяСумма = 0;
ИначеЕсли ТекущаяСумма > МаксимальнаяСумма Тогда
МаксимальнаяСумма = ТекущаяСумма;
КонецЕсли;
КонецЦикла;
//
Вывод = МаксимальнаяСумма;
Заключение:
Интересная была задача и решение, как мне кажется, получилось неплохим и более менее оптимальным!
Задача 2
Задача 3
Задача 4
Задача 5
Заключение:
Платформа: CodeWars
Название задачи: Maximum subarray sum
Ссылка на задачу: https://www.codewars.com/kata/54521e9ec8e60bc4de000d6c (Нажмите на строку)
Сложность: 5 kyu
Тэги: Алгоритмы, Списки, Динамическое программирование, Фундаментальные, Производительность
Оригинальное описание задачи:
The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:
max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) # should be 6: [4, -1, 2, 1]Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.
Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.
Пояснение:
От нас требуется в данном нам массиве, найти последовательность чисел с наибольшей суммой и затем вернуть эту сумму. Например в примере из оригинала, самую большую сумму образует последовательность чисел от 3(индекс) по 6(индекс). Давайте придумаем решение!
Решение:
В первую очередь, само собой, нам необходимо перебрать все элементы исходного массива. Максимальную и текущую сумму будем записывать в заранее объявленные переменные. Далее с каждой итерацией прибавляем к текущей сумме текущее число. Затем проверяем не ушла ли текущая сумма в минус, если ушла то обнуляем. Если всё нормально. проверяем больше ли текущее число чем максимальное число и, если так оно и есть, обновляем максимальную сумму. Опишем это кодом:
ИсходныйМассив = Новый Массив;
ИсходныйМассив.Добавить(-2);
ИсходныйМассив.Добавить(1);
ИсходныйМассив.Добавить(-3);
ИсходныйМассив.Добавить(4);
ИсходныйМассив.Добавить(-1);
ИсходныйМассив.Добавить(2);
ИсходныйМассив.Добавить(1);
ИсходныйМассив.Добавить(-5);
ИсходныйМассив.Добавить(4);
//
МаксимальнаяСумма = 0;
ТекущаяСумма = 0;
Для Каждого Стр Из ИсходныйМассив Цикл
ТекущаяСумма = ТекущаяСумма + Стр;
Если ТекущаяСумма < 0 Тогда
ТекущаяСумма = 0;
ИначеЕсли ТекущаяСумма > МаксимальнаяСумма Тогда
МаксимальнаяСумма = ТекущаяСумма;
КонецЕсли;
КонецЦикла;
//
Вывод = МаксимальнаяСумма;
Заключение:
Интересная была задача и решение, как мне кажется, получилось неплохим и более менее оптимальным!
Quadrants
Ну что ж, пока на этом всё, надеюсь статья была увлекательной для вас, благодарю за внимание. Подключайтесь к решению алгоритмических задач вместе со мной, делитесь вашим мнением и решениями в комментариях! Увидимся в новой статье!
