Software Engineering Note

최대 연속 부분합 찾기 본문

알고리즘/알고스팟

최대 연속 부분합 찾기

devmoons 2014. 8. 16. 15:40

문제: MAXSUM / 구현


역시나 모든 경우를 다 해보면 TLE가 난다. 입력 크기 때문에 O(n^2)도 안될 듯하다.


입력으로 들어올 때 loop 한번에 해결해야 한다.


삽질 몇 번 해보고 나서 어떤 사실을 알게 되었다. 


1) 음수가 부분합에 포함되어도 합한 값이 양수면 어쨌든 나중에 도움이 될 수도 있다. 그러나 음수면 도움이 안된다.

2) 양수들만 모여있는 부분합이 최대 값이 될 수도 있다.


위의 두 가지를 고려해서 변수를 두 개 잡아서 해결했다. 


현재 자신보다 커지는 경우만 선택하는 greedy 한놈, 합한 값이 양수면 안가리고 선택하는 any 한놈.


코드: https://github.com/xgate/algospot/blob/master/IMPL/MAXSUM.cpp


생각해보니 array도 필요 없겠다. 저장할 필요가 없으니 ..


'알고리즘 > 알고스팟' 카테고리의 다른 글

Repeatless Numbers  (0) 2014.08.16
할 일 순서 정하기  (0) 2014.08.16
Brute-Force Attack  (0) 2014.08.16
Decoding  (0) 2014.08.16
Encoding  (0) 2014.08.16