Количество подмассивов сумма которых равна заданному числу

На входе массив чисел, например: arr = [1, -2, 3, 4, -9, 6] .

Задача: найти непрерывный подмассив в arr , сумма элементов в котором максимальна.

Функция getMaxSubSum(arr) должна возвращать эту сумму.

getMaxSubSum([-1, 2, 3, -9]) == 5 (сумма выделенных элементов) getMaxSubSum([2, -1, 2, 3, -9]) == 6 getMaxSubSum([-1, 2, 3, -9, 11]) == 11 getMaxSubSum([-2, -1, 1, 2]) == 3 getMaxSubSum([100, -9, 2, -3, 5]) == 100 getMaxSubSum([1, 2, 3]) == 6 (берём все)

Если все элементы отрицательные – ничего не берём(подмассив пустой) и сумма равна «0»:

getMaxSubSum([-1, -2, -3]) = 0

Попробуйте придумать быстрое решение: O(n 2 ), а лучше за О(n) операций.

Медленное решение

Можно посчитать все возможные подсуммы.

Самый простой путь – посчитать суммы подмассивов, начиная с каждого элемента по очереди.

Например, для [-1, 2, 3, -9, 11] :

// Начиная с -1: -1 -1 + 2 -1 + 2 + 3 -1 + 2 + 3 + (-9) -1 + 2 + 3 + (-9) + 11 // Начиная с 2: 2 2 + 3 2 + 3 + (-9) 2 + 3 + (-9) + 11 // Начиная с 3: 3 3 + (-9) 3 + (-9) + 11 // Начиная с -9 -9 -9 + 11 // Начиная с 11 11

Реализуется с помощью вложенного цикла: внешний цикл проходит по элементам массива, а внутренний считает подсумму, начиная с текущего элемента.

function getMaxSubSum(arr) < let maxSum = 0; // если элементов не будет - возвращаем 0 for (let i = 0; i < arr.length; i++) < let sumFixedStart = 0; for (let j = i; j < arr.length; j++) < sumFixedStart += arr[j]; maxSum = Math.max(maxSum, sumFixedStart); >> return maxSum; > alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5 alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11 alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3 alert( getMaxSubSum([1, 2, 3]) ); // 6 alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100

Это решение имеет оценку сложности O(n 2 ). Другими словами, если мы увеличим размер массива в 2 раза, время выполнения алгоритма увеличится в 4 раза.

Для больших массивов(1000, 10000 или больше элементов) такие алгоритмы могут приводить к серьёзным «тормозам».

Быстрое решение

Идём по массиву и накапливаем текущую частичную сумму элементов в переменной s . Если s в какой-то момент становится отрицательной – присваиваем s=0 . Максимальный из всех s и будет ответом.

Если объяснение недостаточно понятно, посмотрите на код, он вполне лаконичен:

function getMaxSubSum(arr) < let maxSum = 0; let partialSum = 0; for (let item of arr) < // для каждого элемента массива partialSum += item; // добавляем значение элемента к partialSum maxSum = Math.max(maxSum, partialSum); // запоминаем максимум на данный момент if (partialSum < 0) partialSum = 0; // ноль если отрицательное >return maxSum; > alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5 alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11 alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3 alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100 alert( getMaxSubSum([1, 2, 3]) ); // 6 alert( getMaxSubSum([-1, -2, -3]) ); // 0

Этот алгоритм требует ровно 1 проход по массиву и его оценка сложности O(n).

Больше информации об алгоритме тут: Задача поиска максимальной суммы подмассива. Если всё ещё не очевидно как это работает, просмотрите алгоритм в примерах выше, это будет лучше всяких слов.

Разработка алгоритма, обнаруживающего в массиве все пары целых чисел, сумма которых равна заданному значению.

Эту задачу можно решить двумя способами. Выбор определяется компромиссом между эффективностью использования времени, памяти или сложностью кода.

Простое решение

Очень простое и эффективное (по времени) решение — создание хэш-таблицы, отображающей целое число в целое число. Данный алгоритм работает, пошагово проходя весь массив. Для каждого элемента x в хэш-таблице ищется sum – x и, если запись существует, выводится (x, sum – x). После этого x добавляется в таблицу и проверяется следующий элемент.

Альтернативное решение

Давайте начнем с формулировки. Если мы попытаемся найти пару чисел, сумма которых равна z, то дополнение будет z – x (величина, которую нужно добавить к x, что бы получить z). Если мы попытаемся найти пару чисел, при суммировании которых получается 12, дополнением к -5 будет число 17.

Представьте, что у нас есть отсортированный массив . Пусть first указывает на начало массива, а last — на его конец. Чтобы найти дополнение к first, мы двигаем last назад, пока не найдем искомую величину. Если first + last

Разбор по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT – Компанию»

Решения задач с «ACMP — Школа программиста»

На нашем сайте представлены решения задач по программированию с сайта acmp.ru на языке C++, по таким темам как:

Условные операторы и операторы цикла
Строковые типы данных, строки
Одномерные и двумерные массивы
Функции
Сортировки
Рекурсия
Целочисленная арифметика, длинная арифметика
Теория графов
Структуры данных

Номер задачи	Название задачи	Задача
1236	Транспонирование — 4	Транспонирование — 4

Задана целочисленная матрица, состоящая из N строк и M столбцов. Требуется транспонировать ее относительно горизонтали.

Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – количество строк и столбцов матрицы. В каждой из последующих N строк записаны M целых чисел – элементы матрицы. Все числа во входных данных не превышают 100 по абсолютной величине.

Во входном файле INPUT.TXT записано сначала число N — количество вершин графа (от 1 до 100). Далее записана матрица смежности размером N×N, в которой 1 обозначает наличие ребра, 0 — его отсутствие. Матрица симметрична относительно главной диагонали.

Требуется сложить два целых числа А и В.

В единственной строке входного файла INPUT.TXT записано два натуральных числа через пробел, не превышающих 109.

Возможно, что Вы когда то играли в игру «Глухой телефон», либо слышали о ней. В этой игре участникам приходится передавать информацию друг другу различными способами: словесно, образно, бывает даже приходится писать левой рукой текст, который другой участник команды должен будет прочитать. Так же известно, что практически никогда передаваемая информация не доходит до конечного адресата. Обозначим за Fi(x) функцию, которая преобразует текст передаваемой информации x в ту, которую получит участник i+1 от участника i. Тогда последний n-й участник получит данные y, которые будут выражаться следующей формулой:

Но Вам необходимо исключить какие-либо внешние факторы, которые могут исказить исходную информацию и Вы должны реализовать программу «неглухой телефон», которая сможет безошибочно доставлять исходные данные, т.е. в нашем случае функция Fi(x) = x для всех i от 1 до n-1.

В единственной строке входного файла INPUT.TXT записано натуральное число от 1 до 100.

В шкатулке хранится разноцветный бисер (или бусины). Все бусины имеют одинаковую форму, размер и вес. Бусины могут быть одного из N различных цветов. В шкатулке много бусин каждого цвета.

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

Входной файл INPUT.TXT содержит одно натуральное число N — количество цветов бусин (1 ≤ N ≤ 109).

Неспокойно сейчас на стапелях шестого дока межгалактического порта планеты Торна. Всего через месяц закончится реконструкция малого броненесущего корвета “Эния”. И снова этому боевому кораблю и его доблестной команде предстоят тяжелые бои за контроль над плутониевыми рудниками Сибелиуса. Работа не прекращается ни на секунду, лазерные сварочные аппараты работают круглые сутки. От непрерывной работы плавятся шарниры роботов-ремонтников. Но задержаться нельзя ни на секунду.

И вот в этой суматохе обнаруживается, что термозащитные панели корвета вновь требуют срочной обработки сульфидом тория. Известно, что на обработку одного квадратного метра панели требуется 1 нанограмм сульфида. Всего необходимо обработать N прямоугольных панелей размером A на B метров. Вам необходимо как можно скорее подсчитать, сколько всего сульфида необходимо на обработку всех панелей “Энии”. И не забудьте, что панели требуют обработки с обеих сторон.

Во входном файле INPUT.TXT содержатся 3 целых положительных числа N (N ≤ 100), A (A ≤ 100), B (B ≤ 100)

Напишите программу, которая считывает целое число и выводит текст с упоминанием следующего и предыдущего для него чисел.

Входной файл INPUT.TXT содержит целое число, не превосходящее 1000 по абсолютной величине.

Бандиты Гарри и Ларри отдыхали на природе. Решив пострелять, они выставили на бревно несколько банок из-под кока-колы (не больше 10). Гарри начал простреливать банки по порядку, начиная с самой левой, Ларри — с самой правой. В какой-то момент получилось так, что они одновременно прострелили одну и ту же последнюю банку.

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

Определите по этим данным, сколько банок не прострелил Гарри и сколько банок не прострелил Ларри.

В единственной строке входного файла INPUT.TXT записано 2 числа — количество банок, простреленных Гарри и Ларри соответственно.

Вася и Петя учатся в школе в одном классе. Недавно Петя поведал Васе о хитром способе возведения в квадрат натуральных чисел, оканчивающихся на цифру 5. Теперь Вася может с легкостью возводить в квадрат двузначные (и даже некоторые трехзначные) числа, оканчивающиеся на 5. Способ заключается в следующем: для возведения в квадрат числа, оканчивающегося на 5 достаточно умножить число, полученное из исходного вычеркиванием последней пятерки на следующее по порядку число, затем остается лишь приписать «25» к получившемуся результату справа. Например, для того, чтобы возвести число 125 в квадрат достаточно 12 умножить на 13 и приписать 25, т.е. приписывая к числу 12*13=156 число 25, получаем результат 15625, т.е. 1252=15625. Напишите программу, возводящую число, оканчивающееся на 5, в квадрат для того, чтобы Вася смог проверить свои навыки.

В единственной строке входного файла INPUT.TXT записано одно натуральное число А, оканчивающееся на цифру 5, не превышающее 4*105.

Требуется определить последнюю цифру натурального числа.

Входной файл INPUT.TXT содержит натуральное число, не превосходящее 109.

Требуется определить число десятков в заданном натуральном числе в его десятичной записи (то есть найти предпоследнюю цифру в числе).

Входной файл INPUT.TXT содержит натуральное число, не превосходящее 109.

Найдите сумму цифр трехзначного натурального числа.

Входной файл INPUT.TXT содержит трехзначное натуральное число.

Портос хочет украсить золотым шитьем свою перевязь. Он знает, что один сантиметр золотого шитья стоит один луидор. Портосу надо вышить N миллиметров перевязи. Причем мастер никогда не возьмется за работу, если ему заплатят меньше, чем стоит работа. И сдачу мастер никогда не отдает.

Какое минимальное количество луидоров Портос должен заплатить мастеру за работу?

Входной файл INPUT.TXT содержит натуральное число N (N ≤ 109) – длина перевязи в миллиметрах.

Даны два натуральных числа. Требуется проверить: делится ли одно из них на другое?

Первая строка входного файла INPUT.TXT содержит два натуральных числа, разделенных пробелом. Числа не превосходят 100.

N школьников желают разделить K яблок между собой. Они рассматривают два способа дележа:

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

Входной файл INPUT.TXT содержит натуральные числа N и K – количество школьников и яблок соответственно (N,K ≤ 109).

В выходной файл OUTPUT.TXT выведите три целых числа через пробел:

Длина Московской кольцевой автомобильной дороги —109 километров. Байкер Вася стартует с первого километра МКАД и едет со скоростью V километров в час. На какой отметке он остановится через T часов?

Первая строка входного файла INPUT.TXT содержит два целых числа V и T – скорость (км/ч) и время поездки в часах соответственно. Числа разделены пробелом. Если V>0, то Вася движется в положительном направлении по МКАД, если же значение V

Однажды, посетив магазин канцелярских товаров, Вася купил X карандашей, Y ручек и Z фломастеров. Известно, что цена ручки на 2 рубля больше цены карандаша и на 7 рублей меньше цены фломастера. Также известно, что стоимость карандаша составляет 3 рубля. Требуется определить общую стоимость покупки.

В единственной строке входного файла INPUT.TXT записаны три натуральных числа X, Y и Z через пробел, каждое из которых не превышает 109.

Из книги Джонатана Свифта мы знаем, что тот Гулливер посетил страну «Лилипутию», где живут лилипуты, окруженные вещами, животными и заводами небольшого размера. Сначала лилипуты боялись Гулливера, но позже они поняли, что такое соседство приносит им большую выгоду, и они стали помогать ему. Например, лилипуты делали кровать для Гулливера из своих маленьких матрацев, сшитых вместе. Лилипутам были известны размеры Гулливера. Довольно быстро они смогли просчитать количество матрацев, необходимых для шитья большого матраца. Но у них постоянно возникали сложности с их небольшим ростом и стеля постель, они иногда не могли сшить достаточно толстый матрац.

Входной файл INPUT.TXT содержит два целых числа, которые разделены пробелом: K – коэффициент, отражающий во сколько раз Гулливер больше лилипутов, и M – количество слоев матрацев (2 ≤ K, M ≤ 100).

Петя, Катя и Сережа делают из бумаги журавликов. Вместе они сделали S журавликов. Сколько журавликов сделал каждый ребенок, если известно, что Петя и Сережа сделали одинаковое количество журавликов, а Катя сделала в два раза больше журавликов, чем Петя и Сережа вместе?

В единственной строке входного файла INPUT.TXT записано одно натуральное число S – общее количество сделанных журавликов (S < 106).

Даны значения двух моментов времени, принадлежащих одним и тем же суткам: часы, минуты и секунды для каждого из моментов времени. Известно, что второй момент времени наступил не раньше первого. Определите, сколько секунд прошло между двумя моментами времени. Программа на вход получает три целых числа – часы, минуты, секунды, задающие первый момент времени и три целых числа, задающих второй момент времени. Выведите число секунд между этими моментами времени.

Входной файл INPUT.TXT содержит две строки, в каждой из них записан момент времени: в первой строке – начальный, во второй – конечный. Каждое описание времени состоит из трех целых неотрицательных чисел: H, M и S – часы, минуты и секунды (H ≤ 23, M ≤ 59, S ≤ 59).

Найти 2 элемента массива, сумма которых равна заданному числу

Дан массив целых чисел, упорядоченный строго по возрастанию. Дано некоторое число X, нужно менее чем за квадратное количество операций(то есть перебор всех пар) найти такие два любых элемента массива, что их сумма равна X, иначе вывести 0. Как сделать это меньше, чем за квадратное время?

Отслеживать
13.7k 12 12 золотых знаков 43 43 серебряных знака 75 75 бронзовых знаков
задан 22 окт 2015 в 18:11
323 1 1 золотой знак 3 3 серебряных знака 10 10 бронзовых знаков

4 ответа 4

Сортировка: Сброс на вариант по умолчанию

Решение за О(n):
Решаем методом «2 указателя»
Храним 2 индекса: первый сначала указывает на нулевой элемент, второй — на последний элемент.
Цикл — пока индексы не будут равны (то есть пока они не укажут на один и тот же элемент. Если такое случилось — значит, искомых элементов в массиве нет).
На каждой итерации цикла сравниваем текущую сумму (сумму элементов, на которые указывают индексы) с искомой. Если сумма меньше — увеличиваем первый индекс, если сумма больше — уменьшаем второй индекс. Если равна — решение найдено.

#include #include using namespace std; int main() < int *a; // массив int n; // количество элементов в массиве int sum; // необходимая сумма /// //чтение массива cin >> n; a = new int[n]; for (int i = 0; i < n; i++) cin >> a[i]; cin >> sum; /// // индексы int lt = 0; // первый, то есть левый int rt = n - 1; // второй, то есть правый while (lt != rt) < int cursum = a[lt] + a[rt]; if (cursum < sum) lt++; else if (cursum >sum) rt--; else // if (cursum == sum) < cout > cout

Отслеживать
ответ дан 22 окт 2015 в 19:41
835 1 1 золотой знак 6 6 серебряных знаков 22 22 бронзовых знака
Как такой метод найдёт все варианты пар? Хотя в задаче ОП это, вроде бы, не требуется.
22 окт 2015 в 19:52

@Sergiks не «вроде бы», а не требуется. А если потребуется — при нахождении не выходить из программы, заменить «return 0» на «rt—; lt++; «, ну то есть продолжать поиск

22 окт 2015 в 19:56
Классный вариант.
22 окт 2015 в 20:43

Поскольку массив отсортирован, то этим фактом можно воспользоваться для поиска второго элемента в паре с помощью бинарного поиска. Алгоритм следующий:

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

Т.о. получим алгоритм со сложностью O(nlogn): цикл дает O(n), бинарный поиск дает O(logn).

bool found = false; for (int i = 0; i < array.Length; i++) < int first = array[i]; int second = X - first; // искомый элемент int index = BinarySearch(array, second); if (index >-1 && index != i) < Console.WriteLine("and ", i, index); found = true; break; > > if (!found)

Отслеживать
ответ дан 22 окт 2015 в 18:42
25.1k 4 4 золотых знака 46 46 серебряных знаков 81 81 бронзовый знак

да, согласен, но если изменить условие так: нельзя пользоваться сторонними алгоритмами; нельзя использовать коллекции или другие готовые реализации методов

22 окт 2015 в 18:52
@Lescott: Если это учебная задача, то не позорьтесь, прося нас решить её за вас.
22 окт 2015 в 20:24
Нет, это задача просто на оценку времени сложности, интересно было про разные подходы узнать)
23 окт 2015 в 3:16

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

Т.о. один раз пройти, вычисляя дополнения до X, и макс. 2 раза, разыскивая совпадения. И по результатам, исключить дубли зеркальных пар, как (-3,15) в примере ниже.

Недостаток – нужно хранилище для 2 x размер данных . Это оптимизируется, но не будем усложнять.

Пример:

X = 12, исходный ряд: -3 1 3 4 7 9 12 15 -3 1 3 4 7 9 12 15 дополнения до X: 15 11 9 8 5 3 0 -3 двигаем пошагово указатель на текущий элемент в каждом ряду от меньших к большим, если бОльшее значение в одном ряду, в другом ряду берём следующее, если равны, то для след. шага сравнения берём по след. значению в обоих -3 1 3 4 7 8 12 15 -3 0 3 5 8 9 11 15 Находим -3, значит, пара (-3, 12 - -3 = 15); второе совпадение (3, 12-3=9); третье совпадение (15, 12-15=-3);

Надо ещё пройтись по результатам и убрать зеркальные дубли пар, если есть (тут один случай).

Upd не рассмотрел случай, если дополнение = значению и повтор одинаковых значений в исходном массиве, напр. [1,3,3,4,4] .

Количество подмассивов сумма которых равна заданному числу