[LeetCode] 53. maximum subarray (Brute-Force와 카데인 알고리즘) (python 풀이)

nums = [-2,1,-3,4,-1,2,1,-5,4]

이 배열에서 가장 큰 합을 가진 부분 배열은 [4,-1,2,1], 최대합은 6이다

 

어떻게 구해야 할까?

 

# Brute Force

카데인 알고리즘이 생각나지 않는다면 Brute Force 접근법으로 풀어야한다!

Brute-Force란, 모든 경우의 수를 다 구해본 후에 max값을 찾는것

풀이를 간략하게라도 적어보자면,,

1. nums의 index 0부터 시작해서 nums[0]과 함께할수있는(?) 모든 부분합을 구한다.

2. nums[0]의 가능한 모든 부분합 중 가장 큰 값을 변수/리스트/..에 저장

3. 나머지 index 1부터 n-1까지 '1','2' 반복

4. 그러면 리스트던지, 변수던지, 각 인덱스에 해당하는 큰 값들이 모아짐

5. 그 중에서 가장 큰 값을 출력하면 됨

 

이 방식은 풀이만 봐도 정말 비효율적이다..

배열의 크기가 작으면 물론 금방 풀리겠지만, 커지면 커질수록 '1-2'번 반복횟수가 많아지므로, 시간 복잡도는 O(n^2)가 된다

 

따라서 나는 "카데인 알고리즘"으로 접근했다

#카데인 알고리즘

예시로 들어 설명하면

nums=[-2,-1,5,-3]

일단 가볍게 아래와 같은 아이디어?로 시작한다

 

 

1. (자기자신 vs 자기자신+이전값) 들 중 큰값들만 선정

따라서 -2일땐 -2, -1일땐 -1, 5일땐 5, -3일땐 2

 

2. 1번 중 가장 큰 값 -> 5

 

 

 

 

이때, 조금만 더 생각해보면

어짜피 같은 값을 더해주니까 굳이 모든 값을 비교해볼 필요가 없다..

 

따라서,

1.  max(자기자신 vs 자기자신+이전값 중 가장 큰 값)

따라서 -2일땐 -2, -1일땐 -1, 5일땐 5, -3일땐 2

 

2. 1번 중 가장 큰 값 -> 5

 

 

 

 

"이전 값"을 사용하는 것이 가장 큰 핵심 포인트다!

 

여기서 나는 1번에 배열을 생성하여 저장하지 않고,

max(자기자신 vs 자기자신+이전값 중 가장 큰 값) = localMax 값과 이전 max값을 비교하여 globalMax 변수에 큰 값을 저장해서 풀었다..

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        localMax = nums[0]
        globalMax = nums[0]
        for i in range(1,len(nums)):
            localMax = max(nums[i],localMax+nums[i])
            globalMax = max(localMax,globalMax)
        return globalMax

배열 순회를 한번만 하므로, 카데인 알고리즘의 시간복잡도는 O(n)이다.