Bài số 1:
Em nhận xét là khi xét tới thằng thứ i thì ta có 2 trường hợp:
_ Đặt dấu + trước A_i: cái này thì mình cần biết giá trị max_am (tức là tổng lớn nhất mà số cuối cùng của tổng đó là số âm)
_ Đặt dấu - trước A_i: cái này thì mình cần biết giá trị max_duong (tương tự max_am)
Vậy chỉ cần chạy 1 vòng lặp vừa sử dụng 2 biến đó vừa cập nhật lại giá trị cho nó => độ phức tạp O(n)
Code:
max_am:=0;
max_duong:=A[1];
for i:=2 to n do
begin
am:=max_duong - A[i];
duong:=max_am + A[i];
if am>max_am then max_am:=am;
if duong>max_duong then max_duong:=duong;
end;
writeln(max(max_duong,max_am));