Помощь - Поиск - Пользователи - Календарь
Полная версия: Подмассив
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Egor Vladimirovich
Подскажите как решать задачку. Условие. Дан массив.Найти максимальную сумму из всех подмассивов. wacko.gif
Michael_Rybak
Пусть дан массив a. За один линейный проход слева направо заполняем второй массив f такой, что f[i] означает наибольшую возможную сумму из всех подмассивов а, в которых правый конец - это i-й элемент.

f[0], очевидно, равно a[0]

для всех остальных значений понятно, что f[i] = a[i] + max(0, f[i - 1])

Наибольшее из всех f [i] и будет ответом.
Egor Vladimirovich
2 Michael_Rybak
Не могли бы вы написать такую процедуру. Я новичек и особо не разбераюсь в програмировании! За подсказку спасибо. :D
Michael_Rybak
Мог бы smile.gif

type TAr = array [1 .. 100] of integer;
function Solve(n: integer; var a: TAr): integer;
var f: TAr;
i: integer;
ans: integer;
begin
f[1] := a[1];
ans := f[1];
for i := 2 to n do
begin
f[i] := a[i];
if f[i - 1] > 0 then
f[i] := a[i] + f[i - 1];

if f[i] > ans then
ans := f[i];
end;

Solve := ans;
end;

{пример использования}
var x: TAr;
begin
x[1] := 2;
x[2] := 3;
x[3] := -1;
x[4] := 4;
x[5] := -5;
Writeln(Solve(5, x));
end.
Egor Vladimirovich
Огромное Спасибо! Тему можно закрыть) good.gif good.gif good.gif good.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.