파이문

수열에서 연속된 구간의 최대 합 구하기Largest Sum Contiguous Subarray / Maximum subarray problem 유명한 문제로, 주어진 수열에서 최대 합을 구하는 것이 요점이다. 쉽게 생각하자면 O(n^2)으로 구하면 되지만 (Brute Force), 대부분의 문제 풀이 사이트에서는 O(n)으로 풀기를 권고하고 있다. 제일 무난 한것이 Dynamic Programming으로 푸는 것인데, Kadane’s Algorithm이라고 한다. 현재 까지의 구간의 최대 합과, 해당 숫자와 Max 값을 비교하고 이 값을 다시 전체 합과 Max 값을 비교하는 것이다.class Solution: def maxSubArray(self, nums): """ :type nums: List[int..