반응형
<코드>
#include<iostream>
#include<algorithm>
using namespace std;
int x, N;
int dp[100001];
int main()
{
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> x;
if (i == 0)
{
dp[0] = x;
}
else
{
if (dp[i - 1] < 0) dp[i] = x;
else dp[i] = dp[i - 1] + x;
}
}
sort(dp, dp + N, greater<>());
cout << dp[0];
}
| INDEX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Arr | 10 | -4 | 3 | 1 | 5 | 6 | -35 | 12 | 21 | -1 |
| DP | 10 | 6 | 9 | 10 | 15 | 21 | -14 | 12 | 33 | 32 |
DP[x]의 값은 DP[x-1]값과 Arr[x]의 값을 합한 값인데 만약 DP[x-1]이 0보다 작을 경우 DP[x]의 값은 Arr[x]의 값이된다. 이렇게 하여 구한 DP의 최대값이 정답이 된다.
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
반응형
'🧩PS > 🥈Nomal' 카테고리의 다른 글
| [C/C++] 백준 1541번 - 잃어버린 괄호(Greedy) (1) | 2020.12.02 |
|---|---|
| [C/C++] 백준 2579번 - 계단 오르기(DP) (0) | 2020.12.02 |
| [C/C++] 백준 2565번 - 전깃줄 (LIS) (0) | 2020.11.28 |
| [C/C++] 백준 11054번 - 가장 긴 바이토닉 부분 수열 (0) | 2020.11.26 |
| [C/C++] 백준 11053번 - 가장 긴 증가하는 부분 수열 (LIS) (0) | 2020.11.26 |