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

Khó

mảngquy hoạch động6 test · 3 giây

Cho dãy n số nguyên. Tìm đoạn con liên tiếp (ít nhất một phần tử) có tổng lớn nhất và in ra tổng đó.

Thuật toán Kadane giải được trong O(n). Dùng vòng lặp lồng nhau O(n²) sẽ bị quá thời gian với test lớn.

Dữ liệu vào

Dòng 1: n (1 ≤ n ≤ 10⁵).

Dòng 2: n số nguyên (−10⁹ ≤ aᵢ ≤ 10⁹).

In ra tổng lớn nhất (có thể vượt 32-bit, dùng số nguyên 64-bit).

Input

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

Output

Đoạn [4, -1, 2, 1] có tổng 6

Input

3
-5 -2 -9

Output

-2

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.