Подскажите как решать задачку. Условие. Дан массив.Найти максимальную сумму из всех подмассивов.
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];