PTQMSEQ - Dãy số vòng tròn
Giới hạn- Thời gian: 0.243s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Leaxtanh là cháu của nhà thông thái Anhxtanh hiện tại đang làm 1 học sinh chuyên tin. Anh đã đem lòng yêu mến cô bạn chuyên toán cùng khóa từ lâu nhưng chưa được đáp ứng. Vì là 1 học sinh chuyên toán nên cô nàng muốn thử thách leaxtanh bằng một bài toán như sau :
Trên một vòng tròn người ta đánh dấu n vị trí. Các vị trí được đánh số thứ tự từ 1 đến n theo chiều kim đồng hồ. Tại vị trí i người ta ghi số nguyên a[i] (i=1..n). Cần tìm cách chọn ra dãy con độ dài k liên tiếp ( 0<k<n) trên vòng tròn ( theo chiều kim đồng hồ ) để tổng các số hạng trong dãy con này là lớn nhất.
Các bạn hãy nể tình Anhxtanh giúp Leaxtanh nhé.
Input
- Dòng đầu tiên ghi số n
Có 2 kiểu input
- Ghi ra các số a[i], mỗi số cách nhau 1 dấu cách.
- Ghi ra các số a[i], mỗi số trên 1 dòng.
Output
1 dòng duy nhất là tổng các số hạng của dãy tìm được.
Còn lại không in ra gì.
Example
Input: 7 2 -4 1 -7 4 6 -1 Output: 11
Giới hạn |a[i]| <=70000; n<=1094782;
- Người up: vankiepsau95
- Nguồn bài: HSG tỉnh Thanh Hóa