연속된 배열에서 최대 부분합 찾기

Kadane’s Algorithm동적 계획법 DP에 기반한 알고리즘입니다.현재까지의 최대값을 유지하며, 새로운 값이 포함될 때마다 최대값을 업데이트한다는 것이 핵심배열을 처음부터 끝까지 순회하면서 현재 요소를 포함할지 여부를 결정합니다.현재 위치에서 가능한 최대 부분합을 f(Current)라고 가정하고, 이전까지의 현재 배열의 요소를 f(N)이라고 했을 때 경우의 수가 발생한다. 💡기존의 부분 배열에 요소가 추가되는 경우f(Current) + f(N) > f(N)인 경우이 경우는 현재 위치 이전에서 가능한 최대 부분합에 현재 위치의 배열 요소를 더했을 때 가장 큰 값이 된다는 의미로 최대 부분합 배열의 일부임을 의미합니다.새로운 부분 배열이 시작되는 경우f(Current) + f(N) 이 경우는 현재 ..