B. MAXSUM - Đoạn con có tổng lớn nhất

Bộ nhớ: 256 MiB Thời gian: 100 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

Nguồn: Beginner Free Contest 1

Cho mảng A gồm N phần tử. Tìm dãy con S gồm các phần tử liên tiếp của dãy A sao cho tổng tất cả các phần tử của S là lớn nhất.

Dữ liệu vào:

  • Dòng đầu, chứa số nguyên dương N (1 ≤ N ≤ 1000) ;
  • Dòng tiếp theo gồm N số nguyên A_i (−10^9 ≤ A_i ≤ 10^9) .

Dữ liệu ra:

  • Gồm một số nguyên duy nhất là kết quả bài toán.

Ví dụ:

Dữ liệu vào:
3
1 -3 3

Dữ liệu ra:

3