음수는 더하면 손해다. 하지만 음수의 포함한 구간이 더 큰 수를 나타낼 수도 있다.
[ 6, -4, 10, -20, 5, 4 ] 같은 경우에는 [ 6, -4, 10 ]= 12 로 최대이다.
처음부터 수를 누적하면서, 합이 음수가 되면 합을 초기화한다. 그리고 합은 더할때마다 가장 최대값을 따로 저장해둔다.
그럼 합이 음수가 되어 합이 초기화 되는 순간 "하나의 구간"이 구분되고, 따로 저장된 최대값은 "그 구간 내에서 나올 수 있는 최대 합"이 된다.
댓글 없음:
댓글 쓰기