일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 함수형 사고
- coursera
- clean code
- 개발자로살아남기
- 데이터야놀자
- 클린코드
- 데이터유통
- datalake
- 박종천
- 데이터플랫폼
- functional thinking
- 2016년회고
- Raw-Request-URI
- 테스트주도개발
- 알고스팟
- 해커컵
- 동시성
- 단위테스트
- spray
- 개발자
- 코딩인터뷰
- 데이터레이크
- 2017회고
- 회고
- 켄트백
- hackercup2017
- kafka
- wait region split
- 개발7년차매니저1일차
- 실전사례
Archives
- Today
- Total
Software Engineering Note
최대 연속 부분합 찾기 본문
문제: 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
'알고리즘 > 알고스팟' 카테고리의 다른 글
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 |