continuous sum segment tree (1) 썸네일형 리스트형 184. Continuous Sum Segment Tree DP로 해결할 수 있는 문제 중 수열에서 최대 연속합을 구하는 문제가 있다. 이전에 소개한 적이 없으므로 여기서 소개를 하자면 다음과 같다. 아래 문제를 보자. BOJ 1912. 연속합 (Silver II) $n$개의 수가 주어지고 그것을 각각 $a_1, a_2, \ldots, a_n$이라고 했을 때 두 인덱스 $i$와 $j$를 잘 정해서 $a_i + a_{i + 1} + \ldots + a_{j - 1} + a_j$가 최대가 되도록 해야 한다. 세 번째 예제에서 볼 수 있듯이 모든 수가 음수인 경우에도 최소 하나의 수를 골라야 한다. 이 문제를 DP로 풀기 위해 식을 세워 보자. $j$가 $1$인 경우부터 $n$인 경우까지 각각에 대해 해당 조건에서의 최대 연속합 $m_j$를 구하고 거기서 가장 큰 .. 이전 1 다음
