Leetcode - Maximum Subarray (https://leetcode.com/problems/maximum-subarray/)
Leetcode에서 요즘 30-Day LeetCoding Challenge를 하고 있길래 바로 시작했다.
매일마다 한 문제씩 올라오고, 그것을 풀면 보상을 주는 모양이다.
프로그래머스나 백준만 풀다보니 Leetcode나 Codility는 별로 신경 안쓰고 있었는데, 생각보다 Leetcode가 맘에 드는 요소가 많더라.. 무료 회원으로 즐겨보고 프리미엄은 나중에 고려해야할듯 :)
접근 방법
이 문제의 경우, 상당히 유명한 문제이며 백준에서도 연속합 이라는 이름으로 만나볼 수 있는 문제다.
(https://www.acmicpc.net/problem/1912)
분명히 2년 전에 풀었던 기억이 나는데, 다시 풀어보려고 하니 명쾌한 솔루션이 떠오르지 않아서 많이 반성했다 😇
결국 위키백과와 GeeksForGeeks를 통해 복습을 해서 문제를 풀었고, 내가 이해한 내용을 조금 정리해보려고 한다.
참고로 한국어 위키백과에는 이 내용이 없지만, 영어 위키백과에는 Maximum subarray problem 문서에 자세히 설명되어 있다.
이 문제는 Kadane's Algorithm 이라는 O(N) 해법이 존재하며, 동적계획법 (DP) 임에도 불구하고 전혀 어렵지 않으니 잘 알아두면 좋다 😄
Kadane’s Algorithm은 주어진 배열을 한번 슥 훑어서 최대 부분 배열을 구하는데, 그 방식은 아래와 같다.
nums[] = 전체 배열,maxSum[] = 최대 부분 배열합을 저장하고 있는 배열이라고 가정하였을 때maxSum[i] = 마지막 인덱스가 i이면서 nums[i]를 포함하는 부분 배열 중, 가장 최대값을 가지는 부분 배열의 합maxSum[i] = max(maxSum[i-1] + nums[i], nums[i])- 이렇게 구해진 maxSum의 최대값을 별도 변수에 저장해놓으면, 배열을 한번 더 스캔하지 않고 바로 최대값을 출력할 수 있다.
설명을 조금 어렵게 썼는데, 직전 인덱스까지의 최대값과 현재 인덱스값을 더하는게 이득인지 아니면 현재 인덱스값만 취하는게 이득인지만 판단하면 된다고 생각하면 된다.
예를 들어 nums[] = [2, 5, -17, 9] 라고 가정해보자.
1) 0번째 인덱스(nums[0])
-> 0번째 인덱스가 배열의 첫 값이고, 여기서 나올 수 있는 부분 배열은 1개 뿐이니 maxSum[0]은 자연스럽게 2가 된다.
2) 1번째 인덱스(nums[1])
-> 1번째 인덱스의 경우 0보다 큰 자연수이며, maxSum[0]에 더해주었을 때 무조건 이득이 되는 숫자다.
maxSum[0] 역시 0보다 큰 자연수이므로, 버리지 않고 여기에 더해주면 된다.
maxSum[1] = max(2+5, 5) = 7
3) 2번째 인덱스(nums[2])
-> 2번째 인덱스의 경우 음수이기 때문에, 직전 인덱스까지의 최대값이 양수였다면 이를 더해주는 것이 이득일 것이고 그렇지 않은 경우 버리는 것이 이득일 것이다.
이 예시의 경우에는 maxSum[1]이 양수였기 때문에 버리지 않고 더해주면 된다.
maxSum[2] = max(7 + -17, -17) = -10
4) 3번째 인덱스(nums[3])
-> 마지막 인덱스의 경우 양수이며, 이전 인덱스까지의 최대값이 음수였기 때문에 현재 인덱스값만 취하는 것이 이득이다.
maxSum[3] = max(-10 + 9, 9) = 9
maxSum[0…3] 중 가장 큰 값인 9가 정답임을 알 수 있다.
이런 식으로, 배열을 한번 순회하는 것만으로도 정답을 구할 수 있다.
참고
주의할 점이 있다면 maxSum의 최대값을 저장할 별도 변수의 초기화 이슈가 있을 것 같다.
배열에 들어있는 모든 숫자가 0 이상이라면 문제될 것이 없으나, 모든 숫자가 음수인 경우에는 별도 변수의 초기화 값이 0인 케이스에서 올바르게 동작하지 않을 것이기 때문이다.
따라서 문제에서 제시하는 조건을 잘 확인해보고, int의 최소값이나 long의 최소값 등으로 초기화 해주는 것을 권장한다.