Elearning CodePath – CTP Online Judge

Longest Increasing Contiguous Subarray

ISEQ

🟢 Medium #Array #Optimization

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho dãy $A$ gồm $N$ số nguyên.

Yêu cầu:
1.  Tìm dãy con tăng dài nhất gồm các phần tử liền kề trong dãy $A$.
2.  Nếu có nhiều dãy con tăng dài nhất có cùng độ dài, hãy chọn dãy có tổng các số nguyên tố trong dãy là lớn nhất.
3.  In ra độ dài của dãy con tìm được và tổng các số nguyên tố có trong dãy đó.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `ISEQ.INP`:

* Dòng 1: Một số nguyên $T$ ($1 \le T \le 100$) là số bộ dữ liệu.
* $T$ nhóm dòng tiếp theo, mỗi nhóm mô tả một bộ dữ liệu:
    * Dòng đầu: Chứa số nguyên $N$ ($1 \le N \le 10^5$).
    * Dòng sau: Chứa $N$ số nguyên $A_i$ ($1 \le A_i \le 10^9$), các số cách nhau một dấu cách.

---
### 📤 Định dạng Đầu ra

Ghi ra file `ISEQ.OUT` gồm $T$ dòng. Mỗi dòng chứa độ dài dãy con tăng liền kề dài nhất và tổng các số nguyên tố trong dãy của bộ dữ liệu tương ứng. Hai số cách nhau bởi một dấu cách.

---
### ✨ Ví dụ

| Input | Output |
| :--- | :--- |
| `2` `10` `2 3 5 7 4 1 6 5 4 8` `5` `2 2 2 2 2` | `4 17` `1 2` |

---
### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | $T=1$; $1 \le N \le 10^2$; $1 \le A_i \le 10^3$ | $20\%$ |
| 2 | $T=1$; $10^2 \le N \le 10^5$; $10^3 \le A_i \le 10^6$ | $20\%$ |
| 3 | $T=10$; $10^2 \le N \le 10^3$; $A_i \le 10^6$ | $30\%$ |
| 4 | Không có ràng buộc bổ sung ($T \le 100$; $N \le 10^5$; $A_i \le 10^9$) | $30\%$ |

---

✅ Đã AC: 12 / 25 submissions