#1671. DÃY CON ĐAN DẤU (MAXALTSUM)

Cho một dãy số nguyên gồm phần tử ().

Một dãy con được gọi là dãy con đan dấu nếu với mọi , phần tử và trái dấu nhau (tức là ).

Nhiệm vụ của bạn là tìm một dãy con đan dấu có độ dài lớn nhất có thể. Trong trường hợp có nhiều dãy con cùng đạt độ dài cực đại, hãy chọn dãy con có tổng các phần tử là lớn nhất.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên () — số lượng bộ dữ liệu (test cases).
• Mỗi bộ dữ liệu gồm hai dòng:
  • Dòng thứ nhất chứa số nguyên ().
  • Dòng thứ hai chứa số nguyên ().
• Tổng các giá trị của trên tất cả các bộ dữ liệu không vượt quá .

Kết quả:

• Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất là tổng lớn nhất của dãy con đan dấu dài nhất tìm được.

Ví dụ:

Dữ liệu:

4
5
1 2 3 -1 -2
4
-1 -2 -1 -3
10
-2 8 3 8 -4 -1 5 3 3 10
7
1 -10 10 -20 20 -30 30

Kết quả:

2
-1
15
1

Giải thích:

• Ví dụ 1: Các đoạn cùng dấu là và . Chọn số lớn nhất mỗi đoạn là và . Tổng: .
• Ví dụ 2: Chỉ có một đoạn cùng dấu . Chọn số lớn nhất là .
• Ví dụ 3: Các đoạn là , , , . Chọn các số lớn nhất mỗi đoạn: . Tổng: .
• Ví dụ 4: Các phần tử đã đan dấu sẵn. Tổng các phần tử: .

Giới hạn:

• Subtask #1 (15% số điểm): .
• Subtask #2 (20% số điểm): .
• Subtask #3 (10% số điểm): với mọi .
• Subtask #4 (15% số điểm): với mọi .
• Subtask #5 (40% số điểm): Không có ràng buộc bổ sung.