Leetcode 53.Maximum Subarray(Kadane, brute-force algorithm)

문제. 숫자형 array nums가 주어졌을 때 인접한 subarray 중 가장 큰 sum 을 반환하라

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

https://leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

 

---

처음 접근은 for문으로 i를 이동시키면서 end문을 통해 길이가 다른 subarray를 모두 계산 하도록 하는 방법이었는데, time limit 에러가 계속 발생했다...

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        #divide and conquer??
        max_sum = 0
        end = len(nums)
        
        while True:
            for i in range(len(nums)):
                if i <= end:
                    max_sum = max(max_sum,sum(nums[i:end]))
                    end -= 1
        return max_sum

 

---

다른 사람 답변)

 

class Solution:
	def maxSubArray(self,A):
    	cursum = maxSum = A[0]
        for num in A[1:]:
        	cursum = max(num,cursum+num)
            	 maxsum = max(maxsum,cursum)
        return maxsum

 

가끔 답변을 보다보면 힘이 빠질 때가 있는데 이번이 그렇다.

로직을 보면 현재값, 현재값 + 다음값을 더 했을 때 큰 값을 현재값으로 정하고, max값과 지속적으로 비교해서 최대합을 결국 반환하도록 했다. 

 

class Solution(object):
	def maxSubArray(self,nums):
    	arr = []
        arr.append(nums[0])
        maxSum = arr[0]
        
        for i in range(1,len(nums)):
        	arr.append(max(arr[i-1]+nums[i],nums[i]))
            if arr[i] > maxSum:
            	maxSum = arr[i]
        return maxSum

 

이 풀이도 사실 원리는 위와 같다. 다만, arr를 비어있는 리스트로 주고 값을 인덱스로 호출해서 max를 비교하도록했다.

 

---

Discussion을 보니 이 문제가 Kadane's Algorithm이라고 해서 알고리즘을 함께 공부해봤다

먼저, 처음으로 접근했던 Brute Force 알고리즘을 먼저 살펴보자

 

Brute Force Algorithm (브루트 포스 알고리즘) -> Time complexity O(n^2)

 모든 경우의 수를 따지는 직관적이고 비효율적인 접근의 알고리즘을 의미한다. freeecodecamp의 예시를 따르자면, 4자리 비밀번호를 까먹었을 때, 0000부터 9999까지 10000번의 시도끝에 비번을 찾는 노가다 방법이다.  

 

예를 들어 arr = [1,2,3]이라는 배열이 주어지면

조합	현재 합계	최대 합계
[1]	1	1
[1,-2]	-1	1
[1,-2,3]	2	2
[-2,3]	1	2
[3]	3	3

이런식으로 모든 경우의 수에서 합을 구하고 모든 경우의 수를 다 계산하고, 최대합계 중 최대를 계산하는 형태인 것이다

여기서 시간 복잡도를 생각해보면 컴퓨터는 n + (n-1) + (n-2) +... 1의 계산을 하기 때문에 (n*(n+1))/2인 O(n**2)의 시간 복잡도를 가진다. Time exceed에러가 난 것도 이때문이었다

 

따라서, 여기서 이용해야 하는 알고리즘이 바로 Kadane 알고리즘이다.

 

 

Kadane's Algorithm (카데인 알고리즘) -> Time complexity O(n)

앞선 접근보다 훨씬 효율적인 알고리즘으로, 부분배열의 최대 합을 앞선 부분배열 최대합을 이용해서 계산을 하는 방법이다.

위의 예시를 다시 보자면

[1]      -> 1

[1,2]   -> (1) + 2

[1,2,3]-> (1+2) +3

 

결국 부분 배열의 최대 합 = 이전 부분 배열의 최대합 + 다음값을 이용하는 것이다.

 

Source: Geeksforgeeks

이 때문에, 위의 코드와 마찬가지로 기본적인 접근법이

현재값 = max값 = 0으로 초기화 시키고

for loop을 통해서 인덱스 이동을 시키는 장치를 만들고

계산 할 때마다, 현재값에 새로운 계산값을 더해서 업데이트 하고

그 값을 다시 기존의 최대값과 비교해서 마지막에는 결국 전체 부분 배열의 최대값이 도출되도록 하는 것이다.

 

이런 식으로 계산을 하는 컴퓨터의 입장에서 봤을 때 배열을 한번만 돌면 되기 때문에 O(n)의 시간 복잡도를 가진다

 

---

(Source : Rohit Singhai)

그림을 보면서 둘의 접근 방식 차이를 명확하게 이해해보자!

Brute Force와 Kadane Algorithm 비교

Brute Force _ (Source: Rohit Singhai)

Kadane Algorithm _ (Source: Rohit Singhai)

 

참고자료:

https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

Largest Sum Contiguous Subarray (Kadane's Algorithm) - GeeksforGeeks

https://medium.com/@rsinghal757/kadanes-algorithm-dynamic-programming-how-and-why-does-it-work-3fd8849ed73d

Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work?