Re: Проблема «maximum-subarray» на примере курса доллара

[tzlom]

Я бы вам поставил плюсик.

[5erg]

А я б пива поставил :-)

[5erg]

за всякую пуйню плюсуют :-\

[defuz]

так что там на счет пива?)

[butaji]

Спасибо за замечание к статье.

Задача была выдернута мною из контекста упомянутой в статье книги, где показывают как деление задачи на части позволяет оптимизировать время работы алгоритма, код был практически целиком воспроизведен оттуда.

[defuz]

Так вы бы так и написали: Принцип «разделяй и властвуй» может помочь вас оптимизировать ваши алгоритмы. Сейчас я вам покажу, как этот принцип работает на такой-то задаче…
Вы же описывали решение конкретной задачи.

[defuz]

Для двухмерного варианта задача решается точно также динамически за 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).
Если хотите, я могу подробно описать алгоритм в отдельной статье.

[mikhanoid]

Побольше алгоритмов хороших и разных :)

[runnig]

да, напишите пожалуйста!

[tvolf]

При присвоении значения в currentMin вот тут:
===
if v < currentMin:
currentMin, currentMinIndex = v, i
===
еще необходимо дополнительно «сбрасывать» значения maxDiff и bestResult, иначе возможна ситуация, когда найденный максимум будет предшествовать значению найденного минимума. Если, конечно, это важно, и я правильно понял суть задачи )

[defuz]

Суть поняли правильно, но ситуация, которую вы описали невозможна, так как с любой момент времени currentMin — это минимум на промежутке от 0 до i, а за «максимум» на каждой итерации мы принимаем i-ый элемент.

[tvolf]

Я что хотел показать. Допустим, есть вот такая последовательность целых чисел:
1 5 2 4 0 1 1
Перед заходом в «0» у нас минимальный элемент будет равен первой единице, а
maxDiff равен 4 (5-1 = 4). Затем, пройдя все остальные элементы, минимум у нас обновится и будет указывать на «0», а maxDiff так и останется равным 4, по-прежнему указывая на «5» (если я нигде не ошибся :) То есть, функция возвращает просто максимальную разницу и позицию максимального элемента, а уж сам минимум нужном потом будет отыскать дополнительно где-то среди элементов, которые лежат перед полученным в итоге максимальным, так?

[defuz]

В bestResult хранятся позиции минимума и максимума в виде кортежа, соответствующие текущему maxDiff. Как раз эта переменная и обновляется вместе с maxDiff.
В конце цикла на вашем примере значения будут такими:
currenctMin = 0 # глобальный, но не обязательно лучший минимум
currenctMinIndex = 4 # eго значение
maxDiff = 4 # наилучший результат
bestResult = (0, 1) # индексы "наилучших" экстремумов, соответствующие maxDiff


[defuz]

currenctMinIndex = 4 # eго индекс

[tvolf]

Да, действительно, у вас же возвращается кортеж bestResult, где первым значением будет индекс минимального элемента на момент обновления maxDiff. Всё верно. Спасибо большое.

[zubrabubra]

есть кстати задача у которой лучшее решение O(n ln n), но она подразумевает noncontiguous (т.е. 1, 3, 2, 4, 3, 6, 4, 5 => 1, 2, 3, 4, 5).

[Azy]

извращенцы )

print max(A)+min(A)

O(n)×2, но у нас программисты дороже железа

[defuz]

Во-первых, вы видимо имели ввиду print max(A)-min(A), а во-вторых по условию минимум должен предшествовать максимуму.

[Azy]

пардоньте )
как всегда желание быть самым умным контролирует руки лучше чем здравый смысл

[Disasm]

На разнице доллара к рублю можно зарабатывать по-разному. Имея доллары и имея рубли.

[defuz]

Тут вы правы — если автору предыдущего топика было неважно продавать или покупать, то все, что ему нужно было сделать, это max(A)-min(A). :)
Но я все же хотел рассмотреть решение maximum-subarray в чистом виде.

[Disasm]

Кстати, а почему ваше решение корректно? Ведь может быть минимум (не абсолютный), предшествующий абсолютному минимуму и абсолютный максимум, который тоже ему предшествует, такие, что разница будет больше, чем в вашем случае. А у вас получается что допустимые интервалы ограничиваются сразу абсолютным минимумом. Или я неправ?

[defuz]

Не уверен, что правильно понял вас. Приведите пример последовательности.

[Disasm]

10,2,10,100,10,1,10,50,10
Ваше решение даст 50-1 или нет?

[defuz]

Прогнал через функцию: от 2 до 100, то есть 98.

[Disasm]

Теперь и я алгоритм понял. Спасибо.

[Disasm]

Проблема была в трактовке фразы «предшествующим ему абсолютным минимумом». Он или абсолютный на всём отрезке или только на отрезке [0;current]

[defuz]

Только на отрезке [0;current], сейчас поправлю неоднозначность.

[Zibx]

Похожая задача, или эта же была в примерном вступительном в какую-то клёвую питерскую аспирантуру. Пост на хабре ещё был. При решении в голове всплыло слово интегралл, а потом задача как-то превратилась в код.
Задача:
Дан массив 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 )


Хотя не уверен что кому-то будет интересно.