솔찍히 복잡해보이는데 시간초가 어디서 잡아야 할지좀 알려주세요.

전체적인 알고리즘은,

배열 두개를 만들어서 하나는 값을 입력받는 정렬 arr과 arr을 버블정렬로 큰수에서 아래수로 가게끔 tmp를 만들었어요.

tmp[0]이 최대인 수고, arr에서 tmp[0]과 같은 수를 체크하려고 cnt를 넣었구요. arr에서 최대인 수가 몇번째 항인지 검사하기 위함입니다.

그러면 그 항에서부터 우측열, 좌측열로 for문을 통해서 탐색하면서 전 항에 더했던 것과 현재 더하는 것을 비교해서 전항보다 현재항이 작아지면은 break로 탈락시키고 밖으로 나옵니다.

그렇게 우측열과 좌측열에서 더할 수 있는 최대치를 뽑아내고 각 비교를 통해서 더 큰것을 출력하게 만들었는데요.

test케이스는 성공해요.

써놓은 것만 봐도 상당히 복잡해보이긴 하는데 그래도 전 굳이 이걸 써야할 것 같은데(다른 방법은 머릿속에서 안나오네요) 어디서 시간 초과가 나는지 알려주실 분 결초보은 하겠습니다.

chogahui05   4년 전

일단 버블이 O(n^2)라서 시간초과 뜨겠네요..

원본 배열에서 연속적으로 숫자를 선택했을 때 합의 최댓값을 구하는 것이기 때문에 정렬할 필요는 없습니다.

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