Версия для печати темы

Автор: Egor Vladimirovich 13.10.2006 16:21

Подскажите как решать задачку. Условие. Дан массив.Найти максимальную сумму из всех подмассивов.

Автор: Michael_Rybak 13.10.2006 19:27

Пусть дан массив a. За один линейный проход слева направо заполняем второй массив f такой, что f[i] означает наибольшую возможную сумму из всех подмассивов а, в которых правый конец - это i-й элемент.

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

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

Наибольшее из всех f [i] и будет ответом.

Автор: Egor Vladimirovich 14.10.2006 0:15

2 Michael_Rybak
Не могли бы вы написать такую процедуру. Я новичек и особо не разбераюсь в програмировании! За подсказку спасибо. :D

Автор: Michael_Rybak 14.10.2006 3:07

Мог бы

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 14.10.2006 16:41

Огромное Спасибо! Тему можно закрыть)