n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
i
번째 숫자를 선택하느냐, 선택하지 않느냐로 점화식을 전개하는 순간 문제가 수렁에 빠진다.a[0] = 10 = dp[0]
으로 시작한다.a[1] + dp[0] = 6
이 a[1] = -4
보다 크므로 더하는게 이득이다.a[2] + dp[1] = 9
가 a[1] = 3
보다 크므로 더하는게 이득이다.a[7] + dp[6] = -14
가 a[7] = 12
보다 작으므로 여기서 새롭게 시작하는게 이득이다.a[8] + dp[7] = 33
이 a[8] = 21
보다 크므로 더하는게 이득이다.a[9] + dp[8] = 32
이 a[9] = -1
보다 크므로 더하는게 이득이다.dp[0] ~ dp[9]
까지 중 가장 큰 값이 33
이므로 답을 찾을 수 있다.#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n;
cin >> n;
int arr[100001];
for (int i = 0; i < n; ++i) cin >> arr[i];
int answer, dp[100001];
fill_n(dp, n, -1000);
answer = dp[0] = arr[0];
for (int i = 1; i < n; ++i) {
dp[i] = max(dp[i - 1] + arr[i], arr[i]);
answer = max(answer, dp[i]);
}
cout << answer << '\n';
}
#include <cstdio>
int n, a[100000];
int solve() {
int ret = -1000, sum = 0, max = -1000;
for (int i = 0; i < n; ++i) {
sum += a[i];
if (sum < 0) sum = 0;
if (sum > ret) ret = sum;
if (max < a[i]) max = a[i];
}
return (ret == 0) ? max : ret;
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
printf("%d\n", solve());
}