최대 연속 부분합 찾기

문제: MAXSUM / 구현

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

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

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

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

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

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

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

[출처] [AOJ 문제] 최대 연속 부분합 찾기|작성자 DevMoon

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

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

[출처] [AOJ 문제] 최대 연속 부분합 찾기|작성자 DevMoon