LeetCode 53. Maximum SubArray
문제분석
인접한 모든 부분집합에 대해서, 가장 큰 합을 구하기
인풋: [-2,1,-3,4,-1,2,1,-5,4],
아웃풋: 6
설명: [4,-1,2,1] 가 가장 큰 합을 가지고 있다 => 6 return시행착오
내가 처음으로 떠올린 문제 풀이 방법은, 완전탐색 이었다. 배열을 slice 메소드로 인접한 모든 부분집합들을 구한후에, reduce 함수로 합을 구하고, 계속해서 maximum Sum 을 갱신하는 방법이었다.
직관적으로 떠올릴 수 있는 가장 쉬운 방법이지만, 복잡도는 O(n²) 이 된다. 배열을 순회하며 쪼개고, 또 쪼개진 배열에 대해서 순회하며 합을 구하기 때문이다.
따라서, 아래의 코드는 Time Limit Exceed(시간 제한 초과)로 통과하지 못 했다.
돌파구
O(n) 의 복잡도로 한 번만 배열을 순회해서 최대값을 구할 수 있는 알고리즘이 있다. 바로 Kadane’s Algorithm 이라고 불린다.
이 알고리즘은 인접한 부분집합의 최대 합을 구하는 문제를 O(n)의 복잡도로 해결하기 위해서 고안되었다. 일단 이 알고리즘을 살펴보기 이전에, 인접한 부분집합들 중 최대 합을 구하는 문제에 대한 이해를 먼저 해보자.
- 만약 배열의 모든 내용이 양수의 값이라면? => 가장 큰 합을 가지는 부분집합은 배열 그 자체가 될 것이다.
- 위의 경우와 반대로 모든 내용이 음수의 값이라면? => 가장 큰 합을 가지는 부분집합은 배열 중 가장 큰 값이 될 것이다. (음수 들 중 가장 큰 값)
- 각각의 인접한 부분집합들은 같은 최대합을 가질 수 있다.
Kadane’s Algorithm
Kadane’s Algorithm 의 간단한 아이디어는 바로 배열안에서 양수의 값을 찾는 것이다. 최대 합의 성질을 생각 해 보자. 음수는 더하면 손해다. 우리는 최대 합을 리턴하는 함수를 작성하면 되니까, 합에 초점을 맞춰보자.
배열을 한 번 순회하면서, 최대값을 구하기 위해서는 어떻게 해야할까? 갱신할 때!는 바로 이전 배열의 값이 양수 일 때다. 순회하고 있는 현재 배열의 인자에 이전까지 더해온 합이 양수일 때 갱신하면 된다.
예를들어 다음과 같은 인풋에 대해서 배열을 순회하며 최대값을 배열에 갱신하면 다음과 같이 된다.
array: [-2, -3, 4, -1, -2, 1, 5 -3]
최대합으로 갱신 된 배열 구하는 과정:
- index=0: array[-1] = undefined => [-2]
- index=1: array[0] = -2 => [-2, -3]
- index=2: array[1] = -3 => [-2, -3, 4]
- index=3: array[2] = 4 > 0 => [-2, -3, 4, 3(4 + -1)]
- index=4: array[3] = 3 > 0 => [-2, -3, 4, 3, 1(3 + -2)]
- index=5: array[4] = 1 > 0 => [-2, -3, 4, 3, 1, 2(1 +1)]
- index=6: array[5] = 2 > 0 => [-2, -3, 4, 3, 1, 2, 7(5+2)]
- index=7: array[6] = 7 > 0 => [-2, -3, 4, 3, 1, 2, 7, 4(7 + -3)]
최종적으로 갱신된 배열: [-2, -3, 4, 3, 1, 2, 7, 4]
이 중 최대값이 인접한 모든 부분집합들 중 최대합이다.
따라서 7 return
