https://leetcode.com/problems/maximum-product-subarray
152번 문제는 문제 자체가 전형적인 DP 문제처럼 보여서 바로 DP 로 접근했습니다.
음수 와 음수를 곱하면 양수간 된다는 점에서 규칙을 찾아서 문제를 풀었습니다.
DP[i] 는 i 번째까지 최대 값을 가지는 subarray 의 곱셈의 값이고 양수일 경우 index-1 에 현재 값을 곱하면 되지만,
음수일 경우 마지막 음수의 위치에서 현재위치까지 곱한 값을 다시한번 계산하도록 구현했습니다.
https://github.com/sok891111/leetcode/blob/main/WEEK28/152.%20Maximum%20Product%20Subarray.py
이 문제에서 놀라웠던 점은 답을 제출한 이후 다른 사람들이 풀었던 풀이인데요.
-> 방향으로 모든 수를 곱한 후에 <- 방향으로 다시한번 모든 수를 곱해서 최대값이 연속되는 subarray 의 최대값이라는 점입니다.
결국 음수가 홀수 개라면 두 방향 중 한방향에서 최대값이 나오는 관점으로 접근한 풀이인데 개인적으로는 재밌는 접근이라고 생각합니다.
42. Trapping Rain Water 처럼 좌/우 에서 한번씩 계산하는 알고리즘에 대해서도 한번씩 고민할 필요가 있을것 같습니다.