Комментарии 30
Я бы вам поставил плюсик.
Спасибо за замечание к статье.
Задача была выдернута мною из контекста упомянутой в статье книги, где показывают как деление задачи на части позволяет оптимизировать время работы алгоритма, код был практически целиком воспроизведен оттуда.
Задача была выдернута мною из контекста упомянутой в статье книги, где показывают как деление задачи на части позволяет оптимизировать время работы алгоритма, код был практически целиком воспроизведен оттуда.
НЛО прилетело и опубликовало эту надпись здесь
Для двухмерного варианта задача решается точно также динамически за O(n^2). currentMin(i, j) определяется как min(currentMin(i, j-1), currentMin(i-1, j), A[i,j]). Cумма чисел в прямоугольнике вычисляется как S(i,j, u, k) = S(0, 0, u, k) — S(0, 0, u, j) — S(0, 0, k, i) + S(0, 0, i, j).
Если хотите, я могу подробно описать алгоритм в отдельной статье.
Если хотите, я могу подробно описать алгоритм в отдельной статье.
При присвоении значения в currentMin вот тут:
===
еще необходимо дополнительно «сбрасывать» значения maxDiff и bestResult, иначе возможна ситуация, когда найденный максимум будет предшествовать значению найденного минимума. Если, конечно, это важно, и я правильно понял суть задачи )
===
if v < currentMin:
currentMin, currentMinIndex = v, i
===еще необходимо дополнительно «сбрасывать» значения maxDiff и bestResult, иначе возможна ситуация, когда найденный максимум будет предшествовать значению найденного минимума. Если, конечно, это важно, и я правильно понял суть задачи )
Суть поняли правильно, но ситуация, которую вы описали невозможна, так как с любой момент времени
currentMin — это минимум на промежутке от 0 до i, а за «максимум» на каждой итерации мы принимаем i-ый элемент.Я что хотел показать. Допустим, есть вот такая последовательность целых чисел:
1 5 2 4 0 1 1
Перед заходом в «0» у нас минимальный элемент будет равен первой единице, а
maxDiff равен 4 (5-1 = 4). Затем, пройдя все остальные элементы, минимум у нас обновится и будет указывать на «0», а maxDiff так и останется равным 4, по-прежнему указывая на «5» (если я нигде не ошибся :) То есть, функция возвращает просто максимальную разницу и позицию максимального элемента, а уж сам минимум нужном потом будет отыскать дополнительно где-то среди элементов, которые лежат перед полученным в итоге максимальным, так?
1 5 2 4 0 1 1
Перед заходом в «0» у нас минимальный элемент будет равен первой единице, а
maxDiff равен 4 (5-1 = 4). Затем, пройдя все остальные элементы, минимум у нас обновится и будет указывать на «0», а maxDiff так и останется равным 4, по-прежнему указывая на «5» (если я нигде не ошибся :) То есть, функция возвращает просто максимальную разницу и позицию максимального элемента, а уж сам минимум нужном потом будет отыскать дополнительно где-то среди элементов, которые лежат перед полученным в итоге максимальным, так?
В bestResult хранятся позиции минимума и максимума в виде кортежа, соответствующие текущему maxDiff. Как раз эта переменная и обновляется вместе с maxDiff.
В конце цикла на вашем примере значения будут такими:
В конце цикла на вашем примере значения будут такими:
currenctMin = 0 # глобальный, но не обязательно лучший минимум
currenctMinIndex = 4 # eго значение
maxDiff = 4 # наилучший результат
bestResult = (0, 1) # индексы "наилучших" экстремумов, соответствующие maxDiff
есть кстати задача у которой лучшее решение O(n ln n), но она подразумевает noncontiguous (т.е. 1, 3, 2, 4, 3, 6, 4, 5 => 1, 2, 3, 4, 5).
извращенцы )
print max(A)+min(A)
O(n)×2, но у нас программисты дороже железа
print max(A)+min(A)
O(n)×2, но у нас программисты дороже железа
Во-первых, вы видимо имели ввиду
print max(A)-min(A), а во-вторых по условию минимум должен предшествовать максимуму.пардоньте )
как всегда желание быть самым умным контролирует руки лучше чем здравый смысл
как всегда желание быть самым умным контролирует руки лучше чем здравый смысл
На разнице доллара к рублю можно зарабатывать по-разному. Имея доллары и имея рубли.
Тут вы правы — если автору предыдущего топика было неважно продавать или покупать, то все, что ему нужно было сделать, это
Но я все же хотел рассмотреть решение maximum-subarray в чистом виде.
max(A)-min(A). :)Но я все же хотел рассмотреть решение maximum-subarray в чистом виде.
Кстати, а почему ваше решение корректно? Ведь может быть минимум (не абсолютный), предшествующий абсолютному минимуму и абсолютный максимум, который тоже ему предшествует, такие, что разница будет больше, чем в вашем случае. А у вас получается что допустимые интервалы ограничиваются сразу абсолютным минимумом. Или я неправ?
Похожая задача, или эта же была в примерном вступительном в какую-то клёвую питерскую аспирантуру. Пост на хабре ещё был. При решении в голове всплыло слово интегралл, а потом задача как-то превратилась в код.
Задача:
Дан массив a[1]...a[N].
Найти m,k (m<k) такие, что сумма a[m]+...+a[k] максимальна.
Количество операций должно быть O(N).
Писал на том что было рядом — в фаербаге:
Хотя не уверен что кому-то будет интересно.
Задача:
Дан массив a[1]...a[N].
Найти m,k (m<k) такие, что сумма a[m]+...+a[k] максимальна.
Количество операций должно быть O(N).
Писал на том что было рядом — в фаербаге:
var arr = [];
for( var a = 0; a < 20; a++ )
arr.push( Math.round( Math.random() * 100 - 50 ) );
//INIT
var arr2 = []
arr2.push( arr[0] );
var n = 0,m = 0,summ = 0;
var n1,m1;
for( var a = 1; a < 20; a++ ){
var last = arr2[arr2.length - 1];
var current = arr[a];
if( last < 0 ){
last = 0;
n = a;
}
if( last > current ){
if( summ < last ){
summ = last;
n1 = n;
m1 = a - 1;
}
}
arr2.push( (last < 0 ? 0 : last) + current );
}
//OUTPUT
console.log( arr )
console.log( arr2 )
console.log( n1, m1 )
Хотя не уверен что кому-то будет интересно.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Re: Проблема «maximum-subarray» на примере курса доллара