Введение
Традиционные знания часто направляют нас к динамическому программированию для повышения эффективности, когда мы сталкиваемся с проблемами кодирования, связанными с массивами и оптимизацией. Напротив, в этой статье мы рассмотрим интригующую стратегию, которая меняет сценарий. Мы рассмотрим, как добавление массива чисел, отсортированных до нуля, может фактически максимизировать результат при умножении на соответствующий индекс. Мы рассмотрим фундаментальные концепции, лежащие в основе этого нового подхода, и предложим конкретные примеры, иллюстрирующие, как он работает.
Другой подход к решению проблемы сокращения блюд с временной сложностью: O (N log N)
Этот метод был разработан в ответ на программную проблему сокращения блюд. Вот ссылка, по которой вы можете узнать больше о моей стратегии: https://leetcode.com/problems/reducing-dishes/solutions/3930879/kadane-s-algorithm-c-beats-100-users
Подход:
Рассмотрим массив целых чисел: 5, 4, -1, -3, -9. Суммируя элементы в обратном порядке, получаем: 5, 9, 8, 5, -4. Общая сумма останавливается на 5. Теперь давайте рассмотрим тот же массив вместе с соответствующими индексами:
Array: 5, 4, -1, -3 Index: 4, 3, 2, 1
Суммируя произведение каждого элемента и его индекса, получаем: 5 × 4 + 4 × 3 + (-1) × 2 + (-3) × 1 = 20 + 12–2–3 = 27.
Этот инновационный метод обеспечивает максимальную сумму 27, превосходя суммы традиционных подходов, использующих подмножества массива. Например, если выбрать только 5, 4 и -1, получится 22, а включение всего массива — 23.
Исследование шаблона:
Чтобы еще больше укрепить наш подход, давайте рассмотрим случай, когда общая сумма равна нулю. Рассмотрим массив:
7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7
Рассматривая индексы и соответствующие им произведения, мы обнаруживаем, что суммирование элементов массива дает общую сумму 280. Эта интригующая закономерность повторяется в различных целочисленных диапазонах:
+-----------------------+------------------+------------------+-----------------+-------------------+ | Starting Integer (n) | ending at (2-n) | ending at (1-n) | ending at (-n) | ending at (-1-n) | +-----------------------+------------------+------------------+-----------------+-------------------+ | 1 | 1 | 2 | 2 | 0 | | 2 | 8 | 10 | 10 | 7 | | 3 | 25 | 28 | 28 | 24 | | 4 | 56 | 60 | 60 | 55 | | 5 | 105 | 110 | 110 | 104 | | 6 | 176 | 182 | 182 | 175 | | 7 | 273 | 280 | 280 | 272 | | 8 | 400 | 408 | 408 | 399 | | 9 | 561 | 570 | 570 | 560 | +-----------------------+------------------+------------------+-----------------+-------------------+
Доказательство концепции:
Чтобы понять, почему этот подход работает, углубимся в математику. Для данного целого числа n мы разделяем значения массива и индекса на a — b и a + b, получая постоянное значение для b.
Понимание параметров a и b
Когда мы анализируем уравнение, мы сталкиваемся с двумя ключевыми параметрами: a и b. Давайте рассмотрим их значение и то, как они связаны с нашей проблемой.
Интересующий массив, начиная с -n и увеличиваясь на 1 до n, дает нам значения a:
a = -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11
С другой стороны, b остается постоянным и равным b= (включая количество ненатуральных чисел)/2 = (n+1)/2. Например, когда n равно 7, b становится 4:
b = (7 + 1) / 2 = 4
Вывод уравнения полной суммы
Формула для расчета общей суммы основана на наблюдении закономерностей и взаимосвязей между элементами массива и их индексами. Мы можем выразить эту сумму в нескольких формах, каждая из которых проливает свет на разные аспекты проблемы.
Общая сумма = сумма квадратов до ((n+1)/2–1) + сумма квадратов до (n + (n+1)/2) — ((n+1)/2)² * (2n+1 )
Это уравнение инкапсулирует сумму квадратов до определенных диапазонов внутри массива, включая эффект вычитания квадрата члена ((n+1)/2)² * (2n+1).
Общая сумма = сумма квадратов до ((n-1)/2) + сумма квадратов до ((3n+1)/2) — ((n+1)/2)² * (2n+1)
Общая сумма = [(n³)/24 — n/24] + [9(n³)/8 + 9(n²)/4 + 11n/8 + 1/4] + [- (n³)/2–5(n²) )/4 — n — 1/4]
Разбивая сумму на составляющие, мы можем наблюдать отдельные вклады разных членов.
Общая сумма = 2(n³)/3 + (n²) + 1/3n
Этот математический анализ дает представление о механике нашего подхода и подчеркивает взаимосвязь между элементами массива, их индексами и полученной суммой.
Случай 1: суммирование только положительных результатов
Когда мы рассматриваем массив целых чисел, включающий только положительные числа, подход становится простым. Общая сумма в этом случае упрощается до суммы квадратов натуральных чисел. Математически это можно выразить так:
Общая сумма = n(n+1)(2n+1)/6
Общая сумма = n³/3 + n²/2 + n/6
Этот простой подход приводит к получению общей суммы, равной половине ранее рассчитанной суммы, включая отрицательные значения. Поэтому очевидно, что этот подход не может дать сумму большую, чем та, которая получается при рассмотрении отрицаний. Этот вывод также наглядно подтверждается графиком ниже.
График, показывающий сравнение общих сумм только для положительных и отрицательных значений.
Случай 2: Исключение некоторых негативов
Рассматривая сценарий исключения некоторых отрицательных чисел, мы можем наблюдать интригующие закономерности. Давайте рассмотрим пример, где мы начинаем с -5 для массива из 7 элементов.
+---+---+-------+-------+---------------+ | a | b | array | index | multiplied | |---+---+-------+-------+---------------| | -2| 3 | -5 | 1 | -5 | | -1| 3 | -4 | 2 | -8 | | 0| 3 | -3 | 3 | -9 | | 1| 3 | -2 | 4 | -8 | | 2| 3 | -1 | 5 | -5 | | 3| 3 | 0 | 6 | 0 | | 4| 3 | 1 | 7 | 7 | | 5| 3 | 2 | 8 | 16 | | 6| 3 | 3 | 9 | 27 | | 7| 3 | 4 | 10 | 40 | | 8| 3 | 5 | 11 | 55 | | 9| 3 | 6 | 12 | 72 | | 10| 3 | 7 | 13 | 91 | +---+---+-------+-------+---------------+ Total sum : 273
Анализ механизма исключения
Мы можем выразить общую сумму как:
Общая сумма = [общая сумма, содержащая все указанные минусы] — [((n-1)/2)² + ((3n +1)/2)² — (n²)/2 — n — 1/2)]
Общая сумма = [общая сумма, содержащая все указанные минусы] — 2n²
Поскольку 2n² > 0 для n > 0, можно сказать, что общая сумма уменьшается за счет исключения отрицательных чисел.
Вот суть: постепенно удаляя отрицательные числа, мы эффективно уменьшаем значения как b, так и a. Этот маневр меняет представление некоторых членов уравнения. Следовательно, мы наблюдаем снижение влияния конкретных квадратов, таких как (n-1)/2, (3n+1)/2 и (n+1)/2, а также следующих за ними.
Раскрытие визуальных и математических доказательств
Чтобы проиллюстрировать это явление дальше, мы можем вывести уравнение суммы через a и b. Здесь a представляет начальное отрицательное значение, а b получается из b = n — a.
Общая сумма, содержащая все указанные минусы = сумма квадратов до a + сумма квадратов до 2b+a (= n+b) — b² * 2n
Общая сумма, содержащая все указанные минусы = a(a+1)(2a+1)/6 + (2b+a)(2b+a+1)(4b+2a+1)/6 — (b²)2(b+ а)
Теперь, когда мы удаляем отрицательные числа, мы уменьшаем b и a.
При уменьшении b и a создается разница следующего выражения:
Разность = a² + (2b+a)² — (b²)2(b+a)
Теперь заменим все А на Б. (Поскольку буквы a более заметны)
Разность = (b-1)² + (3b-1)² — 2(b²)(2b-1) = -4b³ + 8b² — 8b + 2
Разница генерируется для каждых 2 отрицательных чисел, исключенных из указанных выше. Так как b уменьшается на -1/2 при каждом исключении 1 отрицательного числа.
Примечательно, что выражение -4b³ + 8b² — 8b + 2 играет ключевую роль. Построение графика этого выражения подтверждает его последовательную отрицательность для b › 0.
Общая сумма, содержащая все указанные негативы — 4b³ +8b² — 8b +2 ‹ Общая сумма, содержащая все указанные негативы
Поскольку — 4b³ +8b² — 8b +2 отрицательно при b≥1/2. Таким образом, общая сумма, исключая негативы, всегда будет меньше общей суммы, составляющей его.
Случай 3: включение большего количества отрицательных чисел
Давайте рассмотрим сценарий, в котором мы намеренно включаем в массив дополнительные отрицательные числа. Это исследование раскрывает еще один уровень сложности, демонстрируя, как расположение элементов влияет на общую сумму при умножении на их соответствующие индексы.
Рассмотрим массив, который начинается с -9 с b = 3:
+----+---+-------+-------+---------------+ | a | b | array | index | multiplied | +----+---+-------+-------+---------------+ | -4 | 5 | -9 | 1 | -9 | | -3 | 5 | -8 | 2 | -16 | | -2 | 5 | -7 | 3 | -21 | | -1 | 5 | -6 | 4 | -24 | | 0 | 5 | -5 | 5 | -25 | | 1 | 5 | -4 | 6 | -24 | | 2 | 5 | -3 | 7 | -21 | | 3 | 5 | -2 | 8 | -16 | | 4 | 5 | -1 | 9 | -9 | | 5 | 5 | 0 | 10 | 0 | | 6 | 5 | 1 | 11 | 11 | | 7 | 5 | 2 | 12 | 24 | | 8 | 5 | 3 | 13 | 39 | | 9 | 5 | 4 | 14 | 56 | | 10 | 5 | 5 | 15 | 75 | | 11 | 5 | 6 | 16 | 96 | | 12 | 5 | 7 | 17 | 119 | +----+---+-------+-------+---------------+ Total sum : 255
Такое расположение побуждает нас изучить приращение значений a и b и возникающие в результате сдвиги в общей сумме. Систематический анализ проливает свет на закономерности, возникающие в результате включения большего количества отрицательных чисел.
Наблюдение за приращением
В этом случае и a, и b увеличиваются на 1/2 при каждом добавлении отрицательного числа. Важным наблюдением является то, что увеличение на 1/2 на каждом этапе подчеркивает влияние количества отрицательных элементов на общую сумму. Эта динамика приращения играет ключевую роль в формировании результата.
Раскрытие математического уравнения
Анализируя уравнение, включающее a и b, и то, как они связаны с уравнением общей суммы, мы обнаруживаем основную закономерность. Преобразование уравнения показывает, что в этом сценарии:
Разницу можно легко увидеть, взяв уравнения a и b общей суммы
Общая сумма, содержащая все указанные минусы = a(a+1)(2a+1)/6 + (2b+a)(2b+a+1)(4b+2a+1)/6 — (b²)2(b+ а)
Разница = Общая сумма, содержащая все указанные минусы — Общая сумма Общая сумма, содержащая два дополнительных минуса.
= — [ (a+1)² + (2b+a+1)² — 2(b+1)²(b+a+2) ]
= — [ b² +(3b)² -2(b+1)²(2b+1) ] (Поскольку a = b-1)
= — [ -4b³ — 8b — 2]
= 4b³ + 8b + 2 (+ve)
Поскольку b положительно. Таким образом, выражение является положительным. Следовательно, Общая сумма, содержащая все указанные минусы › Общая сумма, содержащая дополнительные два указанных минуса
Последовательное приращение a и b создает кумулятивный эффект на общую сумму. Этот эффект существенно контрастирует с динамикой, наблюдаемой при выборочном исключении отрицательных чисел.
Построение графика этого выражения подтверждает его последовательную положительность для b › 0.
Еще результаты по интуиции на 7:
+--------------+--------------+--------+ | Starting at | Ending at | Sum | +--------------+--------------+--------+ | 1 | 7 | 140 | | 0 | 7 | 168 | | -1 | 7 | 195 | | -2 | 7 | 220 | | -3 | 7 | 242 | | -4 | 7 | 260 | | -5 | 7 | 273 | | -6 | 7 | 280 | | -7 | 7 | 280 | | -8 | 7 | 272 | | -9 | 7 | 255 | | -10 | 7 | 228 | | -11 | 7 | 190 | | -12 | 7 | 140 | | -13 | 7 | 77 | | -14 | 7 | 0 | +--------------+--------------+--------+
Заключение: раскрытие тонкостей суммирования массивов
Исследование этих различных сценариев иллюстрирует сложную динамику, присущую суммированию массивов. Изучая случаи, связанные с массивами только положительных чисел, выборочным исключением отрицательных чисел и намеренным включением большего количества отрицательных чисел, мы получили ценную информацию.
С помощью математического анализа и визуального представления я обнаружил взаимодействие между элементами массива, их индексами и получающимися общими суммами. Эти случаи демонстрируют тонкий баланс, существующий между положительными и отрицательными элементами, показывая, как эти элементы могут увеличить или уменьшить общий результат.
По сути, это исследование выходит за рамки простой арифметики и раскрывает элегантность и сложность, лежащие в основе, казалось бы, простых задач суммирования массивов. Представляя эти сценарии и их последствия, мы используем новый подход к таким вопросам, когда они возникнут в будущем.
Спасибо за чтение!!!
