Chuyen de 07 - Mang cong don (Prefix Sum)

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Tổng đoạn con lớn nhất 100 1.0s 256M

1. Tổng đoạn con lớn nhất

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tìm tổng giá trị tối đa của một đoạn con khác rỗng.

Input

  • Dòng đầu vào đầu tiên có một số nguyên \(n\): kích thước của mảng.

  • Dòng thứ hai có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): các giá trị của mảng.

Output

  • In một số nguyên: tổng đoạn con lớn nhất.

Example

Test 1

Input 
8
-1 3 -2 5 3 -5 2 2
Output 
9