카데인 알고리즘배열 내 연속된 부분 배열(subarray) 중에서 가장 최대 합을 찾는 알고리즘이다. DP(Dynamci Programming)를 적용한 방식완탐시 O(N^2) 걸리는 거를 O(N)으로!핵심은 각각의 최대 부분합은 이전 최대 부분합이 반영된 결과값이다. MAX(자기 자신 , 바로 이전의 부분합) 파이썬 코드 및 예제def maxSubArray(nums): max_current = max_global = nums[0] for i in range(1, len(nums)): max_current = max(nums[i], max_current + nums[i]) max_global = max(max_global, max_current) ret..
