trang chủ / bài tập / doancon3

Đoạn con 3

Đề bài

Mô tả

Cho một dãy gồm n số nguyên a1,a2,…,an.

Yêu cầu: Hãy chọn ra đúng 3 đoạn con liên tiếp không giao nhau (không có phần tử chung) của dãy sao cho tổng các phần tử trong 3 đoạn con đó là lớn nhất.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên dương n (3≤n≤105).
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (|ai|≤109).

Dữ liệu ra

  • Ghi ra một số nguyên duy nhất là tổng lớn nhất có thể đạt được.

Ví dụ

Input Output Giải thích
7
1 -2 3 4 -1 5 -3		 11 Chọn 3 đoạn con: [1], [3,4] và [5]. Tổng =1+(3+4)+5=13. Hoặc chọn [1], [3,4,−1,5] không được vì chỉ là 2 đoạn. Một cách hợp lệ: [1], [3,4], [5] cho tổng =13.
5
-1 -2 -3 -4 -5		 -6 Buộc phải chọn 3 đoạn, cách tốt nhất là chọn 3 phần tử lớn nhất: [−1], [−2], [−3]. Tổng =−1+(−2)+(−3)=−6.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.400 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0