Svetlanka_87
Новичок
Работа с массивами
Доброй ночи, Господа!
у меня возникла необходимость написания алгоритма поиска в массиве - подмассива с максимальной суммой.
предполагается что числа в массиве могут быть любые
вот пример:
Массив (из 10 чисел): 5 -7 1 2 -3 8 -7 7 -5 4
Подмассив с максимальной суммой будет: 1 2 -3 8 -7 7 его сумма равна= 8
дело в том, что написанный мною алгоритм имеет квадратичную сложность, и для больших объемов информации выполняется довольно долго..
может быть кто-нибудь знает, как можно это сделать линейно ну или хотя бы снизить сложность до логарифмической. Заранее спасибо.
вот мой алгоритм:
Доброй ночи, Господа!
у меня возникла необходимость написания алгоритма поиска в массиве - подмассива с максимальной суммой.
предполагается что числа в массиве могут быть любые
вот пример:
Массив (из 10 чисел): 5 -7 1 2 -3 8 -7 7 -5 4
Подмассив с максимальной суммой будет: 1 2 -3 8 -7 7 его сумма равна= 8
дело в том, что написанный мною алгоритм имеет квадратичную сложность, и для больших объемов информации выполняется довольно долго..
может быть кто-нибудь знает, как можно это сделать линейно ну или хотя бы снизить сложность до логарифмической. Заранее спасибо.
вот мой алгоритм:
PHP:
$max = $a[1]; //макс сумма
$sum = $a[1]; //текущая сумма
$max_l = 1; //левая граница
$max_r = 1; //правая граница
for ($i=1;$i<(n-1);$i++)
{
for($j=2;$j<=n;$j++)
{
$sum=$sum+$a[$j];
if($sum>=$max_temp)
{
$max_temp=$sum;
$max_temp_r=$j;
}
}
if($max_temp>$max)
{
$max=$max_temp;
$max_l=$i;
$max_r=$max_temp_r;
}
}
не так понял задачу.