SUB - Dãy con và đoạn con
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Năm hết Tết đến người người nhà nhà ăn chơi, về quê, đi kiếm gấu nên mình không làm khó các bạn nữa. Bài tập cho các bạn như sau:
Cho một dãy số, tìm:
- Dãy con khác rỗng có tổng lớn nhất
- Đoạn con khác rỗng có tổng lớn nhất
Input
- Gồm nhiều test, dòng đầu tiên là số lượng test ~T~ ~(1 ≤ T ≤ 10)~;
- Mỗi bộ test gồm hai dòng:
- Dòng đầu gồm số lượng phần tử của dãy ~N~ ~(1 ≤ N ≤ 100000)~;
- Dòng tiếp theo gồm ~N~ số nguyên trong khoảng ~[-10^4, 10^4]~
Giới hạn:
- Subtask #1: ~N ≤ 20~;
- Subtask #2: Không có ràng buộc gì thêm.
Output
- Với mỗi bộ test in ra trên một dòng hai số là hai tổng lớn nhất theo thứ tự yêu cầu.
Sample
Input #1
2
4
1 2 3 4
6
2 -1 2 3 4 -5
Output #1
10 10
11 10
Problem source: Kc97ble - Free Contest
Bình luận
Tư tưởng vẫn vậy thôi ae MU nhể =>