Tổng dãy con
Xem PDF
Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho dãy số nguyên gồm \(N\) phần tử. Tìm:
- Dãy con khác rỗng có tổng các phần tử là lớn nhất. (Các phần tử có thể không liên tiếp)
- Dãy con gồm các phần tử liên tiếp có tổng lớn nhất.
Input
- Gồm nhiều test, dòng đầu tiên là số lượng test \(T\) \((1≤T≤10)\)
- Mỗi bộ test gồm hai dòng:
- Dòng đầu là số nguyên dương \(N\) là số lượng phần tử của dãy \((1≤N≤10^5)\)
- Dòng tiếp theo gồm \(N\) số nguyên trong khoảng \([−10^4,10^4]\)
Output
- Với mỗi bộ test, in ra trên một dòng, hai số là hai tổng theo yêu cầu.
Example
Test 1
Input
2
3
4 4 2
5
3 3 -2 3 -4 Output
10 10
9 7
Bình luận
include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int s1(int n) {
int res = 0;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
res += a[i];
}
}
if(res == 0){
res = *max_element(a, a + n);
}
return res;
}
int s2(int n) {
int s = a[0];
int res = a[0];
for (int i = 1; i < n; i++) {
res = max(a[i], res + a[i]);
s = max(s, res);
}
return s;
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cout << s1(n) << " " << s2(n) << endl;
}
return 0;
}
3 bình luận nữa