#617. SUB

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Nguồn: Beginner Free Contest 4

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

Dữ liệu vào:

  • 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]

Dữ liệu ra:

  • 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.

Ví dụ:

Dữ liệu vào:
2
4
1 2 3 4
6
2 -1 2 3 4 -5

Dữ liệu ra:

10 10
11 10

Giới hạn:

  • Subtask \#1 (50\%\text{ số điểm}): N ≤ 20 ;
  • Subtask \#2 (50\%\text{ số điểm}): Không có ràng buộc gì thêm.