Bờm vừa dành chiến thắng trong cuộc thi đặc biệt của Phú ông. Với tính keo kiệt của mình Phú Ông chỉ cho Bờm chọn 1 số phần quà liên tục nhau được đặt sẵn trên bàn. Thật may với bảo bối của Đô-rê-mon Bờm nhanh chóng nhận ra giá trị các phần quà.
Giá trị n phần quà của Phú ông có thể xem là một dãy các số nguyên a1, a2,,an trong đó ai là giá trị của phần quà thứ i. Nếu ai âm thì phần quà đó không có ý nghĩa với Bờm mà ngược lại Bờm lại thấy thật khó chịu vì phải tốn |ai | tiền thuê xe mang nó về nhà rồi cũng chẳng biết làm gì với nó.
Hãy giúp Bờm chọn được một dãy liên tục các phần quà sao cho tổng giá trị là lớn nhất.
Dữ liệu vào: từ tệp MAX1.INP
+ Dòng đầu tiên ghi số nguyên dương n (n10^6)
+ Dòng thứ 2 chứa n số nguyên ai tương ứng với giá trị của phần quà thứ i (|ai|10^9)
Dữ liệu ra: ghi vào tệp MAX1.OUT một số nguyên duy nhất là giá trị của bài toán
Ví dụ:
MAX1.INP
4
1 3 -2 4
MAX1.INP
6
Giải thích: Bờm có thể chọn tất cả các phần quà của Phú ông.
Lời giải 1 :
var n,i,s,p: int64;
arr: array[1..1000005] of int64;
function max(a,b: int64): int64;
begin
if a>=b then exit(a) else exit(b);
end;
begin
readln(n);
for i:=1 to n do read(arr[i]);
s:=arr[1]; p:=arr[1];
for i:=2 to n do begin
p:=max(arr[i],p+arr[i]);
s:=max(s,p);
end;
write(s);
end.
Bạn có biết?
Tin học là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng. Tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin. Hãy tận dụng sức mạnh của tin học để giải quyết các vấn đề và sáng tạo ra những giải pháp mới!
Nguồn :
Wikipedia - Bách khoa toàn thưTâm sự lớp 8
Lớp 8 - Năm thứ ba ở cấp trung học cơ sở, học tập bắt đầu nặng dần và sang năm lại là năm cuối cấp, áp lực lớn dần. Hãy chú ý đến sức khỏe, cân bằng giữa học và nghỉ ngơi để đạt hiệu quả tốt nhất!
Nguồn :
sưu tậpCó thể bạn quan tâm
Copyright © 2024 Giai BT SGK