BÀI TẬP 8 [C++]: ĐOẠN CON

Cho dãy A gồm N số nguyên a₁, a₂, ..., a_n (|a_i| ≤ 10⁹). Một đoạn con a[i..j] có độ dài là j-i+1 (1 ≤ i ≤ j ≤ N). Đoạn con được gọi là đoạn xen kẽ nếu hai phần tử bất kỳ nào đứng cạnh nhau đều trái dấu.

            Yêu cầu của bài tập này bạn cần viết chương trình thực hiện nhiệm vụ sau: Với mỗi vị trí i ( 1 ≤ i ≤ N) hãy tính độ dài dãy con xen kẽ dài nhất của dãy A bắt đầu ở vị trí i.

Dữ liệu nhập: 

            - Dòng đầu ghi T là số lượng bộ test ( 1 ≤ T ≤ 20)

            - Trong 2T dòng tiếp theo ghi thông tin về các bộ test: dòng đầu ghi N, dòng hai ghi dãy A

Kết quả:

- Gồm T dòng, mỗi dòng ghi N số nguyên lần lượt là độ dài dãy con xen kẽ dài nhất tìm được tương ứng với mỗi test trong input.

Ràng buộc:

            - 50% test: 1 ≤ N ≤ 1000

            - 50% test: N ≤ 100.000

Ví dụ:

Input	Output
1 6 -5 -4 -3 1 -2 -1	1 1 3 2 1 1