Dãy con liên tiếp có tổng lớn nhất
Xem dạng PDF
Gửi bài giải
Điểm:
12,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho số nguyên dương N và dãy gồm N số nguyên ~a_1, a_2,…,a_N~.
Yêu cầu: Hãy tìm dãy con gồm các phần tử liên tiếp có tổng lớn nhất.
Input:
- Dòng 1. Ghi số nguyên N.
- Dòng 2. Ghi N số nguyên mỗi số cách nhau ít nhất 1 dấu cách.
Output:
- Ghi số nguyên dương P là tổng các phần tử của dãy con tìm được thỏa mãn các yêu cầu trên.
(Lưu ý: 1 phần tử cũng tính là 1 dãy)
Example:
Input:
6
-16 3 3 3 3 -12
Output:
12
Constraints:
~0 < N \le 10^4; -10^7 \le a_i \le 10^7~
Bình luận
Bài này lm sao ạ! Em lm mà chỉ được 11/12 test
thuật Kadane nha em
.
các bạn cũng có thể dùng tổng tiền tố nhé, có sẵn trên gu gồ👌
co truong hop tong so am khong vay ae
yes
có