Mảng con lớn nhất
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Bạn được cho một mảng gồm ~n~ số nguyên. Nhiệm vụ của bạn là tìm tổng lớn nhất của một đoạn con liên tiếp, không rỗng trong mảng đó.
Đầu vào:
Dòng đầu tiên chứa một số nguyên ~n~: kích thước của mảng.
Dòng thứ hai chứa ~n~ số nguyên ~x₁, x₂, ..., xₙ~: các phần tử của mảng.
Đầu ra:
In ra một số nguyên: tổng lớn nhất của một đoạn con liên tiếp, không rỗng trong mảng.
Ràng buộc:
~1 \le n \le 2 \cdot 10^5~
~-10^9 \le x_i \le 10^9~
Ví dụ :
Input:
8
-1 3 -2 5 3 -5 2 2
Output:
9
Bình luận
include <bits/stdc++.h>
using namespace std; long long n; int main() { cin>>n; long long a; long long cur = LLONGMIN; long long best = LLONGMIN; cin>>a; cur=best=a; for (int i=2;i<=n;i++) { cin >> a; cur=max(a,cur+a); best=max(best,cur); }
}
tham khao la chinh nha