728x90
반응형
이 문제는 DP 문제이다.
1. 수는 한 개 이상 선택해야한다.
2. 수열에서 수를 하나 제거할 수 있다.
수를 제거했을 경우, 수를 제거 하지 않았을 경우로 나누어서 계산한다.
만약 수를 제거 했다면,
현재 위치한 수를 합산하지 않는다면, 여태까지 수열 중 제거한 적이 없는 값
합산한다면 제거한 적이 있는 값
을 비교해서 큰 값을 누적한다.
dp[i][1] = max(arr[i] + dp[i - 1][1], dp[i - 1][0]);
수를 제거하지 않는다면,
현재 위치한 수와 수열 중 제거한 적이 없는 값을 비교해서 큰 값을 누적한다.
dp[i][0] = max(arr[i] + dp[i - 1][0], arr[i]);
따라서 이런 식으로 코드를 작성했다.
// 연속합(2)
#include <iostream>
using namespace std;
int main(void){
int n, arr[100001], dp[100001][2], answer;
cin >> n;
for(int i = 0; i < n; i++){
cin >> arr[i];
}
dp[0][0] = arr[0];
dp[0][1] = 0;
answer = dp[0][0];
for(int i = 1; i < n; i++){
dp[i][0] = max(arr[i] + dp[i - 1][0], arr[i]);
dp[i][1] = max(arr[i] + dp[i - 1][1], dp[i - 1][0]);
answer = max(answer, max(dp[i][0], dp[i][1]));
}
cout << answer;
}
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 합분해 (0) | 2020.11.03 |
---|---|
[algorithm] 백준 - 제곱수의 합 (0) | 2020.11.03 |
[algorithm] 백준 - 가장 긴 증가하는 부분 수열 1 & 4 (0) | 2020.11.03 |
[algorithm] 백준 - 스티커 (0) | 2020.11.02 |
[algorithm] 백준 - 오르막수 (0) | 2020.11.02 |