$maxSum = 0;
$curSum = 0;
for ( $inputArray as $elem ) {
if ( $elem >= 0 ) {
$curSum += $elem;
} else {
if ( $curSum > $maxSum ) {
$maxSum = $curSum;
}
$curSum = 0;
}
}
оптимальный алгоритм
Здравствуйте!
Есть задачка: найти наибольшую сумму непрерывного подмассива в массиве.
Массив называется непрерывным, когда индексы его элементов следеют друг за другом ([5]=>1,[6]=>2,[7]=>3).
Например: массив (1,2,3,-4,5) - наибольшая непрерывная сумма подмассива равна 7 (сумма всех элементов массива). Для массива (1,2,3,-40,5) эта сумма будет равна 5 (сумма первых трех)
Итак, алгоритм:
Слишком тупой:
Не самый оптимальный:
В один цикл:
Но говорят, что существует еще более оптимальый алгоритм решения этой проблемы. Есть предложения?
Есть задачка: найти наибольшую сумму непрерывного подмассива в массиве.
Массив называется непрерывным, когда индексы его элементов следеют друг за другом ([5]=>1,[6]=>2,[7]=>3).
Например: массив (1,2,3,-4,5) - наибольшая непрерывная сумма подмассива равна 7 (сумма всех элементов массива). Для массива (1,2,3,-40,5) эта сумма будет равна 5 (сумма первых трех)
Итак, алгоритм:
Слишком тупой:
Код:
$maxSum = 0;
for ($i=0;$i<count($inputArray);$i++) {
for ($ii=count($inputArray);$ii>0;$ii--) {
$sum = 0;
for ($iii=$i;$iii<$ii-$i;$iii++) {
$sum += $inputArray[$iii];
}
if ($sum>$maxSum)
$maxSum = $sum;
}
}
for ($i=0;$i<count($inputArray);$i++) {
for ($ii=count($inputArray);$ii>0;$ii--) {
$sum = 0;
for ($iii=$i;$iii<$ii-$i;$iii++) {
$sum += $inputArray[$iii];
}
if ($sum>$maxSum)
$maxSum = $sum;
}
}
Код:
$maxSum = 0;
for ($i=0;$i<count($inputArray);$i++) {
if (($inputArray[$i]>0) || check($i))
$maxSum += $inputArray[$i];
else
break;
}
echo $maxSum;
function check($p) {
global $inputArray;
$sum = 0;
for ($i=$p+1;$i<count($inputArray);$i++) {
if (($inputArray[$i]>0) || check($i))
$sum += $inputArray[$i];
else
return false;
}
if (abs($inputArray[$p])<$sum)
return true
else
return false;
}
for ($i=0;$i<count($inputArray);$i++) {
if (($inputArray[$i]>0) || check($i))
$maxSum += $inputArray[$i];
else
break;
}
echo $maxSum;
function check($p) {
global $inputArray;
$sum = 0;
for ($i=$p+1;$i<count($inputArray);$i++) {
if (($inputArray[$i]>0) || check($i))
$sum += $inputArray[$i];
else
return false;
}
if (abs($inputArray[$p])<$sum)
return true
else
return false;
}
Код:
$maxSum = 0;
$sum = null;
$n = false;
$negVal = 0;
for ($i=0;$i<count($inputArray);$i++) {
if ($inputArray[$i]>0) {
$sum += $inputArray[$i];
if ($n && ($sum>0)) {
$n = false;
$sum = $maxSum + $sum;
}
}
else {
if (!is_numeric($sum)) {
if ($i==0 || ($negVal< $inputArray[$i]))
$negVal = $inputArray[$i];
}
else {
if (!$n) {
$n = true;
$maxSum = $sum;
$sum = $inputArray[$i];
}
else
$sum += $inputArray[$i];
}
}
echo $sum."\r\n";
}
if (!is_numeric($sum))
$maxSum = $negVal;
elseif ($maxSum<$sum)
$maxSum = $sum;
echo $maxSum;
$sum = null;
$n = false;
$negVal = 0;
for ($i=0;$i<count($inputArray);$i++) {
if ($inputArray[$i]>0) {
$sum += $inputArray[$i];
if ($n && ($sum>0)) {
$n = false;
$sum = $maxSum + $sum;
}
}
else {
if (!is_numeric($sum)) {
if ($i==0 || ($negVal< $inputArray[$i]))
$negVal = $inputArray[$i];
}
else {
if (!$n) {
$n = true;
$maxSum = $sum;
$sum = $inputArray[$i];
}
else
$sum += $inputArray[$i];
}
}
echo $sum."\r\n";
}
if (!is_numeric($sum))
$maxSum = $negVal;
elseif ($maxSum<$sum)
$maxSum = $sum;
echo $maxSum;
Что-нибудь в таком духе:
Это, если мы учитываем непрерывные пустые подмассивы. В этом случае максимальная сумма 0, если все элементы массива отрицательные, иначе равна максимальной из сумм последовательных неотрицательных элементов.
Это, если мы не учитываем пустые непрерывные подмассивы. В этом случае сумма равна максимальному элементу, если все элементы отрицательны, иначе равна максимальной из сумм последовательных неотрицательных элементов.
По асимптотике быстрее, чем O(n) здесь ничего быть не может. Величина константы - вопрос открытый, но думаю, что что-то намного быстрее придумать сложно.
Это, если мы учитываем непрерывные пустые подмассивы. В этом случае максимальная сумма 0, если все элементы массива отрицательные, иначе равна максимальной из сумм последовательных неотрицательных элементов.
Код:
Это, если мы не учитываем пустые непрерывные подмассивы. В этом случае сумма равна максимальному элементу, если все элементы отрицательны, иначе равна максимальной из сумм последовательных неотрицательных элементов.
Код:
$maxSum = null;
$curSum = null;
for ( $inputArray as $elem ) {
if ( $elem >= 0 ) {
if ( !is_numeric( $curSum ) ) {
$curSum += $elem;
} else {
$curSum = $elem;
}
} else {
if ( !is_numeric( $maxSum ) || $elem > $maxSum ) {
$maxSum = $elem;
}
if ( is_numeric( $curSum ) && $curSum > $maxSum ) {
$maxSum = $curSum;
}
$curSum = null;
}
}
$curSum = null;
for ( $inputArray as $elem ) {
if ( $elem >= 0 ) {
if ( !is_numeric( $curSum ) ) {
$curSum += $elem;
} else {
$curSum = $elem;
}
} else {
if ( !is_numeric( $maxSum ) || $elem > $maxSum ) {
$maxSum = $elem;
}
if ( is_numeric( $curSum ) && $curSum > $maxSum ) {
$maxSum = $curSum;
}
$curSum = null;
}
}
По асимптотике быстрее, чем O(n) здесь ничего быть не может. Величина константы - вопрос открытый, но думаю, что что-то намного быстрее придумать сложно.
Цитата: GHopper
Есть задачка: найти наибольшую сумму непрерывного подмассива в массиве.
Массив называется непрерывным, когда индексы его элементов следеют друг за другом ([5]=>1,[6]=>2,[7]=>3).
Например: массив (1,2,3,-4,5) - наибольшая непрерывная сумма подмассива равна 7 (сумма всех элементов массива). Для массива (1,2,3,-40,5) эта сумма будет равна 5 (сумма первых трех)
Массив называется непрерывным, когда индексы его элементов следеют друг за другом ([5]=>1,[6]=>2,[7]=>3).
Например: массив (1,2,3,-4,5) - наибольшая непрерывная сумма подмассива равна 7 (сумма всех элементов массива). Для массива (1,2,3,-40,5) эта сумма будет равна 5 (сумма первых трех)
Кстати, это задача на динамическое программирование (сродни дискретной задаче об укладке рюкзака), нужно кэшировать промежуточные суммы, возможно вечерком предложу свое решение. И еще. Вы путаете терминологию. В вашем случае, это не массивы, это таблицы (хэш-таблицы), так как массив подразумевает участок памяти с последовательным расположением элементов, где каждый элемент имеет индекс - номер своей позиции.
Блин.. Еле врубился :)
Я так понял суть задачи - найти такие последовательные элементы массива, сумма которых была бы максимальной (сумма никаких других последовательных элементов не была бы больше найденной). Верно?
Я так понял суть задачи - найти такие последовательные элементы массива, сумма которых была бы максимальной (сумма никаких других последовательных элементов не была бы больше найденной). Верно?
Задача решена. http://www.rosettacode.org/wiki/Maximum_subarray.
Сам не знал, что сумма не может быть отрицательной...
Сам не знал, что сумма не может быть отрицательной...
Цитата: GHopper
Сам не знал, что сумма не может быть отрицательной...
А как насчет массива (-1,-2,-3,-4,-5) ???
Цитата: Phodopus
А как насчет массива (-1,-2,-3,-4,-5) ???
А как насчет по ссылке сходить?!
"Given an array of integers, find a subarray which maximizes the sum of its elements, that is, the elements of no other single subarray add up to a value larger than this one. An empty subarray is considered to have the sum 0; thus if all elements are negative, the result must be the empty sequence."
Цитата: GHopper
А как насчет по ссылке сходить?!
Ээээ! Не грубить! При чем тут ссылка и изначально поставленное вами условие задачи?!
ПыСы. По ссылке все еще "иду". В процессе я..
Цитата: GHopper
Задача решена. http://www.rosettacode.org/wiki/Maximum_subarray.
Сам не знал, что сумма не может быть отрицательной...
Сам не знал, что сумма не может быть отрицательной...
больше всего мне понравилась реализация на языке J...
Кстати изменив две строчки в алгоритме на C он будет работать и с "отрицательными" массивами..
Цитата: Phodopus
А как насчет массива (-1,-2,-3,-4,-5) ???
Т.е. вы хотите сказать, что операция суммирования не определена на отрицательных числах и сумма (какой кошмар) не может быть отрицательным числом?
Цитата: hardcase
Т.е. вы хотите сказать, что операция суммирования не определена на отрицательных числах и сумма (какой кошмар) не может быть отрицательным числом?
Если это ко мне, то я ничего такого сказать не хочу :) Совсем наоборот!
Если все элементы массива отрицательный, то должен вернуться 0. Это условия задачи.
Цитата: GHopper
Если все элементы массива отрицательный, то должен вернуться 0. Это условия задачи.
Если сумма отрицательная, значит вертаем 0. ;)