Dãy con (HSG9 NB 2023)

Điểm: 900 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: daycon.inp

Output: daycon.out

Tác giả:

Sunlight

Dạng bài

Cho dãy số nguyên $A$ gồm $n$ số nguyên $(a_1, a_2, ..., a_n)$ . Một dãy con liên tiếp của $A$ là một dãy con gồm các phần tử liên tiếp nhau trong dãy $A$ .

Yêu cầu: Hãy tìm dãy con liên tiếp có tổng các phần tử lớn nhất.

Input, Output và Subtasks

Input: (daycon.inp)

Dòng đầu ghi số nguyên $n$ ( $0<n\le 10^6$ )
Dòng thứ hai ghi $n$ số nguyên $a_1, a_2, ..., a_n$ ( $|a_i|\le 10^6, 1\le i\le n$ ), mỗi số cách nhau một khoảng trắng

Output: (daycon.out)

Dòng đầu ghi tổng lớn nhất tìm được
Dòng thứ hai ghi ra các phần tử của dãy con liên tiếp tìm được (giữ nguyên theo thứ tự ban đầu trong $A$ ). Mỗi phần tử cách nhau một khoảng trắng. Nếu có nhiều dãy như thế thì in ra dãy xuất hiện đầu tiên

Subtasks

Subtask 1 $(40\%)$ : $n\le 100$
Subtask 2 $(40\%)$ : $n\le 10^4$
Subtask 3 $(20\%)$ : Không có ràng buộc gì thêm

Sample

Input (daycon.inp)

6
-2 3 -2 3 1 -2

Output (daycon.out)

5
3 -2 3 1

Note

Trong các dãy con liên tiếp thì dãy gồm các phần tử 3 -2 3 1 có tổng bằng $5$ là lớn nhất

Bình luận

Không có bình luận nào.