kizkiz12   1년 전

안녕하세요. 파이썬으로 문제를 푸는 과정에서 게시글에 반례를 참고하였는데 해결하지 못해 질문드립니다.

연속된 양수와 음수가 있다면 그 값을 더해 dp[]에 저장하여 음수와 양수가 번갈아 나타나는 배열을 하나 만들었습니다.


dp[]이 앞에서 차례대로 더해나가면서 그 값이 dp[]의 최댓값보다 큰 경우에 배열에 추가하는 코드를 작성하였습니다.

만약 더한 누적 값이 0이 되면 0으로 초기화 후에 다음 값부터 이어서 더하게 작성하였습니다.

시간복잡도는 O(N)이 소요되는 건 지 궁금하고 반례를 찾아주시면 코드 수정해보겠습니다. 

알고리즘 공부는 처음이라 접근이 이상하거나 더 좋은 접근이 있으면 조언 부탁드립니다!

hhs2003   1년 전

반례 찾는게 좀 힘들었습니다.

코드 이해가 아직 부족하여 시간복잡도는 모르겠습니다... 화이팅하세요.

kizkiz12   1년 전

아! 감사합니다.

덕분에 빠르게 해결했어요!

0을 무시하게 코드를 작성하여 예외가 많이 발생했네요 :)

dp[]에 음수만 존재하거나 빈 리스트인 경우, max(lst)를 출력하게 만들어 해결하였습니다.

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