leetcode 알고리즘 - MaximumSubarray

1. 문제 소개

• 주어진 배열에서 최대 부분합을 구하는 문제다.
• leetcode 난이도 easy 수준의 문제다.
• 카데인 알고리즘을 이용하면 O(N)으로 해결할 수 있다.

2. 코드

class Solution:
    # Brute Force - 
    def get_maximum_sum(self,arr:List[int]):
        start = 0 
        end = len(arr)
        maximum_sum=arr[start]
        while(start<end):
            mid=start+1
            pre_sum=sum(arr[start:mid])
            while(mid<end):
                mid+=1
                if pre_sum < sum(arr[start:mid]):
                    pre_sum = 	sum(arr[start:mid])	
            if maximum_sum < pre_sum:
                maximum_sum=pre_sum
            start+=1

        return maximum_sum
    
    def kadane_algorithm(self,arr:List[int]):
        start = 0
        end = len(arr)
        maximum_sub_array = arr[start]
        start=0
        current_sum = 0
        while(start < end):
            current_sum = max(arr[start],current_sum+arr[start])
            if current_sum > maximum_sub_array:
                maximum_sub_array = current_sum
            start+=1

        return maximum_sub_array


    def maxSubArray(self, nums: List[int]) -> int:
        
        return self.kadane_algorithm(nums)

3. 코멘트

• 카데인 알고리즘은 각 최대 부분합을 구할 때 이전 최대 부분합을 이용해서 구하는 것이 핵심이다.
  • 흐름을 텍스트로 설명하자면  
  •  subArray_1 = new element
  •  subArray_2 = subArray_1 + new element
  •  subArray_3 = subArray_2 + new element
  • .. 쭉 배열의 끝까지..
• 각각의 subArray (최대부분합)을 구할 때는 (이전 최대부분합+현재인덱스)과 현재 인덱스를 비교해서 큰 값을 구한다.