ahwlsdn123   2년 전

제가 어쩌다 보니 dp를 쓰지 않고 문제를 풀게 됐습니다. 시간 복잡도가 O(n)이 나왔는데 dp를 써서 정석대로 문제를 풀었을 땐 시간 복잡도가 어느 정도 나오나요?

amsminn   2년 전

dp를 사용한 풀이 또한 O(N)입니다.

아마 dp 테이블을 사용하지만 않았을 뿐 같은 풀이일것이라고 생각합니다.

kadane's algorithm과 같은 키워드로 검색해보시면 좋을 듯 해요.

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