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)

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

      KO HIEU DE


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

        .


        • -4
          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 ạ


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

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

            1 phản hồi

            • 6
              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ì

              1 phản hồi

              • 6
                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 ạ

                1 phản hồi