29 lines
1.6 KiB
Python
29 lines
1.6 KiB
Python
# Maximum Product Subarray
|
|
|
|
class Solution:
|
|
def maxProduct(self, nums: list[int]) -> int:
|
|
answer = nums[0]
|
|
now_max = nums[0]
|
|
now_min = nums[0]
|
|
|
|
for num in nums[1:]:
|
|
temp_min = now_min
|
|
now_min = min(num, now_max * num, now_min * num)
|
|
now_max = max(num, now_max * num, temp_min * num)
|
|
|
|
answer = max(answer, now_max)
|
|
|
|
return answer
|
|
|
|
"""
|
|
걸린 시간: 몰라
|
|
|
|
복잡도: nums 리스트를 한번 순회하는데 이때마다 현재 최대, 최소, 전체 최대 변수만 관리하기 때문에 시간복잡도는 O(n)이고, 공간복잡도는 O(1)이다.
|
|
|
|
해설: 또 못 풀었다. 이 문제의 포인트는 음수가 홀수개이거나, 0이 있을 때 양쪽 중에 어디가 더 최대인가를 판단하는 것이라고 생각했다.
|
|
그 기준점을 나눌 때 본인부터 부분 수열을 시작하게 하면서 이전의 기록들을 어떻게 가져갈지 고민이 되었다.
|
|
왜냐하면 음수가 홀수개일때는 최소인 값들이 음수 하나를 더 만나면 최대값이 될 수도 있기 때문에 기록을 해두면서 가야했다.
|
|
본인이 양수든 음수든 상관없이 현재 최대값과 최소값에 곱해보고 거기서 두 변수를 갱신하면 현재까지의 수열 중 최대를 계속 가져갈 수 있다.
|
|
여기서 가져갈 건 연속된 부분수열의 경우 현재의 것을 무조건 쓰는 경우의 수로 두고 기존과 비교해서 최대를 구해야 한다는 것과
|
|
음수와 0의 존재를 인지하고, 부호가 바뀔 것을 고려하여 현재까지의 최소값도 기록해두는 것이다.
|
|
""" |