최대 부분배열 합(카데인) 계산기

«여기서 끊을까, 이어 붙일까»라는 한 줄 판단이 전부입니다. cur = max(x, cur + x)로 지금까지의 합이 음수면 이어 붙여 봐야 손해이므로 버리고 새로 시작합니다. 이 한 줄 덕분에 모든 시작·끝 짝을 보는 O(n²)이 한 번 훑는 O(n)이 됩니다.

문제가 «빈 구간»을 허용하느냐에 따라 갈립니다. 적어도 한 개는 골라야 한다면 가장 덜 음수인 원소 하나가 답이고, 빈 구간(합 0)을 허용하면 0이 답입니다. 실전에서 가장 흔한 버그가 여기이며, 이 계산기는 두 답을 모두 보여 줍니다.

두 경우 중 큰 쪽을 고릅니다. 가운데를 고르는 경우는 보통의 카데인이고, 끝과 처음에 걸치는 경우는 «전체합 − 최소 부분배열 합»입니다. 다만 전부 음수면 두 번째 식이 전부 빼는 빈 구간을 뜻하게 되어 0이 나와 버리므로 그때는 첫 번째 식만 써야 합니다 — 원형 카데인의 유일한 함정입니다.

음수 둘이 곱해지면 양수가 되기 때문입니다. 지금까지의 최댓값만 들고 가면 −2 같은 값에서 끊어 버려 나중에 다른 음수를 만나 커질 기회를 놓칩니다. 그래서 최솟값도 함께 들고 가다가 음수를 만나면 둘을 맞바꿉니다. 0을 만나면 둘 다 끊깁니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서만 이뤄지고, 입력값은 이 기기의 저장소에만 남습니다.