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

9

Bình luận


  • -1
    ducbao_    8:36 p.m. 31 Tháng 10, 2024
    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)
      • 6 bình luận nữa