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\ \leq \ T\ \leq \ 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\ \leq \ n\ \leq \ 100000)\)

– Dòng tiếp theo gồm \(n\) số nguyên trong khoảng \(\lbrack - 10^{4},\ 10^{4}\rbrack\)

Kết quả:

+ 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ụ: