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

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

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

Bình luận

Hint

Python

n = int(input())
arr = list(map(int, input().split()))

ps = 0
min_ps = 0
max_s = arr[0]

for i in range(n):
    ps += arr[i]
    max_s = max(max_s, ps - min_ps)
    min_ps = min(min_ps, ps)

print(max_s)

Phản hồi

Ziolesyama • 7:43 a.m. 30 Tháng 10, 2024 •

KO HIEU DE

0
Phản hồi Chia sẻ

tung1408 • 10:20 a.m. 21 Tháng 9, 2024 • ← chỉnh sửa 5 →

.

0
Phản hồi Chia sẻ

tk22NguyenMinhPhuc • 5:39 p.m. 20 Tháng 9, 2023 •

test có bị lỗi không vậy ạ sao em nộp kiểu gì cũng bị lỗi runtime vậy ạ

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

-5
Phản hồi Chia sẻ

lehuy_1704209 • 12:43 p.m. 18 Tháng 9, 2023 •

sao ko dùng khai báo "long" đc v ạ :>

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

-5
Phản hồi Chia sẻ

1 phản hồi

dang7rickroll • 8:11 p.m. 5 Tháng 8, 2022 •

làm ơn chỉnh lại memory đi ạ, 5k dùng kiểu gì

8
Phản hồi Chia sẻ

1 phản hồi

PhamtUan123 • 7:54 p.m. 5 Tháng 8, 2022 •

test có bị lỗi không vậy ạ sao em nộp kiểu gì cũng bị lỗi runtime vậy ạ

8
Phản hồi Chia sẻ

1 phản hồi