백준 13398. 연속합 2

https://www.acmicpc.net/problem/13398

13398번: 연속합 2

 

아래 연속합 문제에서 이어지는 문제다.

https://tose33.tistory.com/97

백준 1912. 연속합

다른 점은 이제 수열에서 수를 하나 제거 할 수 있다. 

 

d 정의 

d[0][i] = 수를 하나 제거할수 있는 기회를 아직 안썼고, i 까지의 연속합 중 최댓값 

d[1][i] = 수를 하나 제거할수 있는 기회를 썼고, i 까지의 연속합 중 최댓값 

 

점화식

d[0][i] = max(d[0][i-1]+a[i], a[i]) 

d[1][i] = max ( max(d[0][i-1], d[1][i-1]) + a[i], d[0][i-1]) 

 

d[0][i]는 수를 하나 제거할수 있는 기회를 쓰지 않은 경우이므로 연속합1 문제와 같다.

 

d[1][i]는 수를 하나 제거할수 있는 기회를 이미 쓴 경우 이므로 다음 두 수 중 큰 수가 된다.

max(d[0][i-1], d[1][i-1]) + a[i] 가 의미하는 바는 이전 숫자까지의 연속값중 최대인값 (기회를 썼어도되고 안썼어도 된다)에 현재 숫자를 더한 값이다.

d[0][i-1]이 의미하는 바는 현재 숫자를 포기하는 경우인 d[0][i-1] 중 큰 값이 된다. (현재 숫자를 포기했으므로 기회는 쓴것이다) 

 

 

 

 

---

다른 분들 코드를 보니 이런 방법도 있었다.

left[i] = 0번 숫자 부터 i번째 까지 숫자들의 연속합중 최댓값 

right[i] = 마지막 숫자부터 i번째 까지 숫자들의 연속합중 최댓값 

 

이렇게 두 배열의 값을 구하고 나면 첫번째 숫자부터 마지막 숫자까지 하나씩 없에보면서 상수시간으로 값을 구할수 있다.