whdudgns412   5년 전

실제 코드는 260줄부터입니다.

제 코드 알고리즘은 다음과 같습니다.

[

우선 0들은 집어넣지 않고 zero touch = true를 해줍니다.

모든 수열을 받아서 + - + - + .... - + (양수, 음수, 양수, ...) 로 압축합니다(합칩니다).

예를 들어, 23, 14, -5, -13, 0, 2, 15, -33 의 input이 주어진다면

{37, -18, 17} 이 됩니다. (양쪽 맨끝은 항상 양수가 되도록 음수를 제거합니다)

양수와 음수가 번갈아서 반복되는 형태가 된다면 이제 본격적으로 시작됩니다.

맨 오른쪽 3개를 추출하여 left, mid, right라 할 때,

이를 압축하는 방법은 크게 3가지가 있습니다.

1) left와 right 둘 다 |mid|보다 클 때 -> {... left, mid, right} -> {... left+mid+right} 

나머지 경우 중

2) left >= right일 때 mid의 크기에 상관없이 {... left, mid, right} -> {... left}

3) left < right일 때 {... left, mid, right} -> {... left+mid,right}

3번의 경우 벡터의 끝이 - - + 의 형태가 될수 있는데, left가 음수인지 체크하여 left와 mid를 합쳐줍니다.

이 과정을 벡터의 크기가 2 이하일 때까지 진행 후 case 처리합니다.

getMAX()의 맨 윗부분에서 모두 음수일 경우 처리해 주었습니다.

]

질문에 나온 대부분의 반례를 모두 넣어본 결과 제대로 나오는데, 4%에서 바로 틀렸습니다가 떠버립니다..

만들어본 반례들이나 이미 있는 것들은 다 되는데 안되는 반례를 못찾겠네요ㅜㅜ

도와주세요..

notorioush2   5년 전

코드 어딘가에서 메모리 침범이 일어나는 것 같습니다.

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