CSES - Maximum Subarray Sum | Tổng đoạn con lớn nhất

Xem PDF
Tác giả:
Flower_On_Stone , Elektrikar
Dạng bài
Điểm: 900 Thời gian: 1.0s Bộ nhớ: 512M 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.

Constraints

  • \(1 \leq n \leq 2 \cdot 10 ^ 5\)
  • \(-10 ^ 9 \leq x_i \leq 10 ^ 9\)

Example

Sample input

8
-1 3 -2 5 3 -5 2 2

Sample output

9

Bình luận