참조 : https://medium.com/@aliasav/algorithms-maximum-product-subarray-b09e520b4baf
참조 : https://leetcode.com/problems/maximum-product-subarray/discuss/1608747/Daily-LeetCoding-Challenge-December-Day-3/1169035
관련 문제 : LeetCode No.152 (https://leetcode.com/problems/maximum-product-subarray/)
- 이전 글에서 서술했듯, 카데인 알고리즘은 특정 배열의 가장 큰 부분합을 구하는 알고리즘이다. 이 과정에서 traverse함에 따라 계속 갱신되는 maximum 변수와 result 변수를 설정했었다.
- 하지만 곱셈이라면 어떨까? 가장 큰 부분곱을 구해야 한다면? 원리는 같으나, 음수 곱하기 음수는 양수라는 것을 고려해야 한다.
- 최소곱, 최대곱을 추적하는 두 변수를 각각 만들고, traverse 과정에서 나오는 수가 음수라면, 최소곱과 최대곱을 바꿔 주면 된다. 음수를 곱하면 대소관계가 역전되기 때문.
- 나머지 즉, 시작 인덱스 갱신의 원리나 결과값에서의 최대값 비교는 카데인 알고리즘과 같다. 이런 식으로 최소값도 구할 수 있다.
함께 나아가고자 하는 사람