Maximum Subarray Problem

문제. 가장 큰 연속한 부분합 구하기

 

정수들의 리스트가 입력으로 들어옵니다.

이 정수들의 리스트를 일부분만 잘라내어 모두 더했을 때의 값을 부분합이라 부릅니다.

이때 가장 큰 부분합을 구해봅시다.

 

예를 들어, [-10, -7, 5, -7, 10, 5, -2, 17, -25, 1]이 입력으로 들어왔다면 [10, 5, -2, 17]을 모두 더한 30이 정답이 됩니다.

 

※입력에는 최소 하나 이상의 양수가 존재합니다.

※이 문제에는 여러 종류의 풀이법이 존재합니다. 각 풀이법의 시간 복잡도를 고려하면서 여러가지 방법으로 문제를 풀어 봅시다.

 

def maxSubArray(nums):     return 0   def main():     print(maxSubArray([-10, -7, 5, -7, 10, 5, -2, 17, -25, 1])) # 30이 리턴되어야 합니다   if __name__ == "__main__":     main()

 

 

결론부터

 

Kadane's Algorithm 을 사용하면 된다. (Joseph B. Kadane: http://www.stat.cmu.edu/~kadane/)

- 나는 처음에 멍청하게 Dynamic Programming 으로 풀었다.

 

링크

 

참고 링크

- 한글 블로그: https://blog.naver.com/7005ye/221070006057

- YouTube: https://youtu.be/86CQq3pKSUw (좀더 인싸이트를 얻게 되었다)

 

구현 링크

- GitHub: https://github.com/nicewook/max-sub-array

- Go Playground: https://play.golang.org/p/fNmvqPgo_xu

 

 

Solution. 양수 존재 여부와 상관없이 짜보자

 

- 유튜브 ( https://youtu.be/86CQq3pKSUw ) 를 보고 좀더 체계적인 개념이 잡혔다.

 

1) 순차적으로 index 를 하나씩 올려가며 계산을 하는데

2) 각각의 index 가 마지막 값인 경우들 중에서 최대값을 구해본 다음 (이 개념 이해가 중요하다)

3) 그러한 index 별 최대값들 중에서의 최대값을 찾아내는 것이다.

 

 

예시를 통해 이해해보자

 

입력 배열 tArray 는 {-10, -7, 5, -7, 10, 5, -2, 17, -25, 1} 이라고 하자

 

index	sum 계산
0	index 0 을 마지막으로 하는 연속한 부분 배열은 {-10} 하나 뿐이므로 sum = -10 따라서, maxSum = -10 이다.
1	{-7} 일 경우 sum = -7 {-10, -7} 일 경우 sum = -17 따라서 maxSum = -7
2	{5} sum = 5 {-7, 5} sum = -2 {-10, -7, 5} sum = -12 maxSum = 5
3	{-7} sum = -7 {5, -7} sum = -2 {-7, 5, -7} sum = -9 {-10, -7, 5, -7} sum = -19 maxSum = -2

 

뒤는 생략하였지만 깨닿게 되는 부분이 있다.

1) 현재 index 를 마지막으로 하는 연속된 부분 배열의 합을 계산할때에

2) 현재 바로 앞까지의 합이

- 음수라면 모두 무시하고 현재 index 의 값만을 sum 으로 계산하고

- 양수라면 이를 포함하여 sum 을 계산하면 된다는 것이다.

 

 

이제 코딩해보자

 

index 까지 추적하였더니, 오히려 코드 이해에 방해가 되는 것도 같다. 이 부분은 생략하고 분석해보겠다.   1) index 0 일때의 값을 sum 과 maxSum 에 넣어준다. - sum 은 현재 index 를 마지막 값으로 한 연속한 부분 집합의 합 중에서 가장 큰 값이 되고 - maxSum 은 그야말로 지금까지 가장 큰 값이다. sum of sum   2) index 0 일때는 이미 계산한 것이고, index 1 부터 끝까지 루프를 돌며 계산을 시작한다.   3) 이전까지의 sum 값을 현재 index 의 값과 더하는 것이 더 큰지 아닌지를 판단해서 - 더 큰 값을 sum 으로 한다.   4) 그렇게 계산한 sum 값과 지금까지의 maxSum 값을 비교해서 - 더 큰 값이 maxSum 으로 한다.

 

테스트 부분은 아래와 같다. (Dynamic Programming 은 무시하자)