[JAVA/자바] 백준 13398번: 연속합2

문제 연속합 문제의 업그레이드 버전이다. 알듯 말듯했지만 결국은 풀이를 참고했던^^,, 이 문제는 두가지의 경우로 나누어 풀어야한다. 1.

수를 제거하지 않는 경우 dp[i][0] 2. 수를 하나 제거하는 경우 dp[i][1] 1의 경우는 연속합에서 풀었던대로 풀면된다. 2의 경우가 관건인데 현재 수를 삭제할 것인지, 아니면 이전에 수를 삭제했는지로 나뉜다.

현재 수를 삭제할 것이라면 이전에 삭제 내역이 없는 dp[i-1][0]을 채택해야한다. 현재 수를 삭제하지 않는다면 이전에 삭제 내역이 있는 dp[i-1][1]을 채택한다.

즉 dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1] + 현재 수)로 표현할 수 있다. 이제 여기서 최대값을 구하면 끝!

풀이 htt..........