Описание тега kadanes-algorithm
Алгоритм Кадане - это подход динамического программирования к проблеме максимального подмассива, то есть задача поиска непрерывного подмассива в одномерном массиве чисел (содержащем по крайней мере одно положительное число), который имеет наибольшую сумму.
1
ответ
Как получить стартовый индекс для максимальной суммы подмассива
Я использую следующую программу, чтобы найти максимальную сумму и индексы суммы. Я могу получить правильный индекс, но не могу найти правильный индекс. def max_sum_new(a): max_current = max_global = a[0] r_index = 0 for i in range(1, len(a)): max_cu…
07 фев '19 в 16:20
0
ответов
Максимальная подматрица (2D) при игнорировании не более одного элемента
Я знаю, что алгоритм поиска максимальной 2D подматрицы O(m^2*n) с использованием алгоритма Кадане, где m - столбцы, а n - строки. Но существует ли алгоритм для нахождения максимальной 2D подматрицы, если мы должны игнорировать ровно 1 элемент во все…
09 фев '18 в 19:22
2
ответа
Найти начальный и конечный индекс смежного подмассива наименьшей суммы в C++
Я пытаюсь найти начальный и конечный индекс непрерывного подмассива наименьшей суммы. Я пытался много раз, но я не мог найти. Кто-нибудь может мне помочь с этим в C++? Код для нахождения наименьшей суммы смежных подмассивов: #include <bits/stdc++…
21 ноя '18 в 06:19
3
ответа
Нахождение смежного подмассива с максимальной суммой
Вот моя программа, чтобы найти максимальную сумму подмассива (смежный) из данного массива. это очень легко, используя алгоритм Кадане. #include <iostream> #include <cstdio> using namespace std; int kadane(int a[], int n) { int max_ending…
15 май '15 в 18:26
2
ответа
Понимание алгоритма Кадане для двумерного массива
Я пытаюсь написать программу, которая решает проблему максимального подмассива. Я могу понять интуицию алгоритма Кадана в одномерном массиве, а также реализацию O(N^4) в двумерном массиве. Однако у меня возникли проблемы с пониманием реализации O(N^…
28 сен '13 в 06:38
1
ответ
Максимальная сумма Subarray O(n) не Kadane's
Я читаю "Введение в алгоритмы" Кормена. Для линейного алгоритма для задачи Max Sum Subarray я придумал собственное решение. Не проверял существующий (Кадена) перед внедрением. Сейчас я тестирую его с разными сценариями тестирования и всегда получаю …
22 мар '15 в 19:04
1
ответ
Алгоритм линейного времени для максимальной непрерывной суммы подмассива
Я решал упражнение из Введение в алгоритмы - CLRS и наткнулся на решение максимального смежного подмассива за линейное время (Q 4.1-5). Пожалуйста, посмотрите на мое решение ниже. Я искал онлайн-судей для этого упражнения, но не нашел ни одного. Реш…
11 мар '18 в 06:48
0
ответов
Обновление максимального прямоугольника суммы в разреженной матрице при изменении одного элемента
У меня есть матрица mxn, которая редка с N ненулевых записей. Модифицированная версия Kadane's 2-d algorithm можно найти максимальную сумму под прямоугольника в O(m N log n) время, которое бьет традиционный алгоритм Кадане O(m^2 n) для достаточно ра…
20 янв '14 в 17:33
1
ответ
Динамическое программирование в алгоритме Кадане
Initialize: max_so_far = 0 max_ending_here = 0 Loop for each element of the array (a) max_ending_here = max_ending_here + a[i] (b) if(max_ending_here < 0) max_ending_here = 0 (c) if(max_so_far < max_ending_here) max_so_far = max_ending_here re…
01 май '13 в 18:08
2
ответа
Диапазон максимального массива продукта (вариант алгоритма Кадане)
Я пытался получить диапазон максимального продукта подмассива (готовясь к собеседованиям). Это уже спрашивалось здесь (но никаких действительных ответов предоставлено не было). Получение диапазона максимального массива продукта с использованием алго…
26 май '14 в 04:46
1
ответ
Два крупнейших смежных подмассива
В настоящее время я занимаюсь проблемой, которая похожа на проблему максимального смежного подмассива. Однако вместо того, чтобы найти только один смежный подмассив, я могу найти до двух непересекающихся смежных подмассивов. Например, для теста ниже…
01 янв '17 в 02:45
15
ответов
Максимальная сумма подмассива по модулю М
Большинство из нас знакомы с проблемой подмассива максимальной суммы. Я наткнулся на вариант этой проблемы, который просит программиста вывести максимум всех сумм подмассива по модулю некоторого числа M. Наивный подход к решению этого варианта состо…
29 июн '15 в 11:01
3
ответа
Работает ли алгоритм Max Sub Array от Kadane для всех целых положительных чисел?
Я реализовал проблему с массивом Max Sub в Kavane в javascript, но, похоже, в итоге я всегда получаю 0 в консоли, хотя существуют большие числа (я понимаю, что он делает то, что делает из-за цикла for из 0 - size где size = subarray size). Так как ж…
07 июн '12 в 05:22
11
ответов
Нахождение минимальной абсолютной суммы подмассива
Там есть массив A содержащие (положительные и отрицательные) целые числа. Найдите (непрерывный) подмассив, абсолютная сумма элементов которого минимальна, например: A = [2, -4, 6, -3, 9] |(−4) + 6 + (−3)| = 1 <- minimal absolute sum Я начал с реа…
22 сен '14 в 02:31
1
ответ
Кадане с изюминкой
Проблема: Дано два массива A а также Bоба размера nнайти интервал [i,j] (0 <= i,j <= n-1) что максимизирует значение V = sum(A[i:j]) - min(B[i:j]), Без массива B Твист, эта проблема является просто проблемой максимальной суммы подрешетки, разр…
11 фев '18 в 22:05
1
ответ
Как мне изменить алгоритм Кадане, чтобы найти элементы подмассива, которые вносят вклад в максимальную сумму?
Что я сделал до сих пор: Я узнал сумму, используя алгоритм Кадане. Я создал вектор "res", который хранит элементы при выполнении условий. Проблема: Например, когда входные данные являются массивом: {-2, -3, 4, -1, -2, 1, 5, -3} Массив результатов со…
18 янв '17 в 16:04
2
ответа
Максимальная вариация подмассива
Я должен решить проблему, очень похожую на проблему максимального подмассива. Я должен найти самый большой подмассив, среднее значение которого больше k. Я думал, что следующий трюк. Я могу преобразовать мой массив A[] размера n в B[], где B[i] = A[…
14 ноя '12 в 19:32
2
ответа
Алгоритм Кадане в Scala
У кого-нибудь есть реализация Scala алгоритма Кадане, выполненная в функциональном стиле?
28 янв '12 в 00:22
18
ответов
Алгоритм Кадане Отрицательные числа
int array[] = {-1, 4, -2, 5, -5, 2, -20, 6}; Если бы у меня был этот массив, моя реализация алгоритма Кадане для нахождения максимального подмассива работает: int max_so_far = INT_MIN; int max_ending_here = 0; for (int i = 0; i < size; i++) { max…
30 мар '12 в 11:40
3
ответа
n чисел расположены по кругу. Нам нужно найти максимальную сумму последовательных номеров
Для линейного массива задача поиска максимальной суммы последовательных чисел. это просто. Это может быть легко сделано с помощью алгоритма Кадане., Но теперь массив находится в форме круга, и нам нужно найти максимальную сумму последовательных чисе…
23 июл '12 в 10:09