반응형
<코드>
#include<iostream>
#include<algorithm>
using namespace std;
int n, ans;
int arr[100001];
int dp[100001][2];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
cin >> arr[i];
dp[0][0] = arr[0];
dp[0][1] = arr[0];
ans = arr[0];
for (int i = 1; i < n; i++)
{
dp[i][0] = max(dp[i - 1][0] + arr[i], arr[i]);
dp[i][1] = max(dp[i - 1][0], dp[i - 1][1] + arr[i]);
ans = max(ans,max(dp[i][0], dp[i][1]));
}
cout << ans;
}
풀이 방법
dp[i][0] : 수열의 1~i번째 사이에서 가장 큰 연속 합
dp[i][1] : 수열의 1~i번째 사이에서 하나의 수를 제거했을 때 가장 큰 연속 합
13398번: 연속합 2
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
반응형
'🧩PS > 🥇Hard' 카테고리의 다른 글
| [C/C++] 백준 1774번 - 우주신과의 교감 (MST, 크루스칼) (0) | 2021.02.04 |
|---|---|
| [C/C++] 백준 1197번 - 최소 스패닝 트리 (MST, 프림, 크루스칼 알고리즘) (0) | 2021.02.04 |
| [C/C++] 백준 10986번 - 나머지 합 (1) | 2021.01.26 |
| [C/C++] 백준 2270번 - 하노이 탑 (0) | 2021.01.25 |
| [C/C++] 백준 3908번 - 서로 다른 소수의 합 (0) | 2021.01.25 |