furyhunter   7년 전

동적계획법을 이용해 각 입력의 연속합을 모두 기록하고, 그중 최댓값을 취하는 방식으로 코드를 짜봤는데요..


시간초과가 나네요.. for 중첩을 줄일 수 있는 방법이 있을까요?

chan4928   7년 전

DP[i] = (i번째 수를 구간의 마지막으로 하는 최대 연속구간합)

으로 정의하면

DP[i] = (?)

한 번 생각해보세요! 하실 수 있을 겁니다

isangyoon   7년 전

특별히 배열에 값을 저장안하시고 변수 두개로만으로도 충분히 답을 만들 수 있습니다.


1. 수를 입력받는다.

2. 수의 합을 구해서 그 값이 음수면 그 수부터 다시 계산 시작, 그렇지 않으면 합을 계산

3. 합의 최댓값을 만든다.

4. 최댓값이 답

furyhunter   7년 전

덕분에 잘 해결했습니다!

감사합니다!

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