Nội dung Bài tập
- Mã:
- Maximum_Subarray
- Tên:
- Mảng con tối đa
- Dạng thi:
- oi
- Thang điểm:
- 100 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- 4901104081
Cho một dãy số nguyên gồm n phần tử: x1, x2, x3,..., xn
Quảng cáo
Hãy tìm tổng lớn nhất có thể của một dãy con liên tiếp trong dãy đã cho. Một dãy con liên tiếp là một đoạn con có các phần tử nằm liền kề nhau trong dãy ban đầu.
Input
- Dòng đầu tiên chứa 1 số nguyên n: số lượng phần tử trong dãy.
- Dòng thứ hai chứa n số nguyên x1, x2, x3,..., xn: các phần tử của dãy.
Output
- Một số nguyên duy nhất là tổng lớn nhất có thể của một dãy con liên tiếp trong dãy đã cho.
Constraint
- 1 ≤ n ≤ 2.105
- -109 ≤ xi ≤ 109
Ví dụ:
Input
Output
8
-1 3 -2 5 3 -5 2 2
9
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận