1912 연속합
풀이법
연속 합에서 가장중요한건 구간을 따로 몰라도 된다는 점이다.
이게 무슨말이냐면 우리가 구간의 합을 구할떄 무의식적으로 Left와 Right를 구할려고 한다.
그러면 자동적으로 n^2의 빅오를 가진 알고리즘이 탄생하게된다.
하지만 지금 현재까지 더한값이 0보다 작으면 최대값은 그대로 두고 0보다 크면 최대값을 갱신해주면 된다.
다음은 그 풀이이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include <iostream>
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <vector>
using namespace std;
int maxSum( std::vector<int> &a) {
if (a.size()==0) return a[0];
int min = 0, sum = 0, ret = –1000000;
for (int i = 0; i < a.size(); ++i) {
sum = std::max(sum, 0) + a[i];
ret = std::max(ret, sum);
}
return ret;
}
int main() {
int n;
cin >> n;
std::vector<int> v;
v.resize(n);
for (auto &i : v) {
cin >> i;
}
std::cout<<maxSum(v);
}
|
cs |