qkfskan82   2년 전

우선 코드는 맞았습니다만... 

이해가 안가는 부분이 있어서 반례 찾기 질문 드립니다.

처음 dp를 돌며 이 구간까지 가능한 누적합의 최댓값을 구하고,

다시 dp를 돌며 

하나를 버릴경우 이 구간까지 가능한 누적합의 최댓값 (버렸거나 안버렸거나) or 나를 버릴시 가능한 누적합 중 max를 취해서 저장합니다.

이 경우에 두번째 dp (코드에서 dp[n][1]부분)이 기존의 누적합 dp보다 같거나 크다고 생각했습니다.

그걸로 답을 출력했더니 pass되지 않아 찾아보니 dp[n][0] 과 dp[n][1]을 비교하는 코드가 있더라구요.

Math.max함수를 하나 추가해서 통과는 했지만 뭔가 찝찝해서 더 고민해봤습니다.

생각해보니 가장 첫 원소를 버릴때 최댓값이 나오는 경우가 있을것 같아 첫 원소를 버릴수 있게 하고,

원소가 하나일땐 버릴수 없게 삼항연산자로 처리해봤습니다.

dp[0][1] = (N == 1) ? arr[0] : Math.max(arr[0], 0);              <--요부분

제가 잘못 생각했거나 놓친 반례나 조건이 있다면 알려주시면 감사하겠습니다!

WeissBlume   2년 전

주어지는 수열이 모두 양수로 이루어진 경우는 어떨까요?

댓글을 작성하려면 로그인해야 합니다.