Tổng dãy con

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Thời gian:
Python 3 3.0s
Bộ nhớ:
Python 3 260M
Tác giả:
admin
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số nguyên gồm \(N\) phần tử. Tìm:

  • Dãy con khác rỗng có tổng các phần tử là lớn nhất. (Các phần tử có thể không liên tiếp)
  • Dãy con gồm các phần tử liên tiếp 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 là số nguyên dương \(N\) là số lượng phần tử của dãy \((1≤N≤10^5)\)
    • Dòng tiếp theo gồm \(N\) số nguyên trong khoảng \([−10^4,10^4]\)

Output

  • Với mỗi bộ test, in ra trên một dòng, hai số là hai tổng theo yêu cầu.

Example

Test 1

Input 
2
3
4 4 2
5
3 3 -2 3 -4
Output 
10 10
9 7

Bình luận