우규이인우윤
Eager To Learn 🌌
우규이인우윤
전체 방문자
오늘
어제

블로그 메뉴

  • 🏡 홈
  • 🚀 깃허브
  • ⛅ 태그 클라우드
  • 분류 전체보기 (217)
    • 👨🏻‍💻 PS (170)
      • JAVA (82)
      • MYSQL (1)
      • Docker (2)
      • PYTHON (24)
      • LeetCode 150 (39)
      • Algorithm 기법 (1)
      • 바킹독 (21)
    • 블로그 이사 (0)
    • Error (1)
    • CS (15)
      • DataBase (2)
      • OS (7)
      • Network (1)
      • Spring (1)
      • 자료구조 (3)
      • Java (1)
    • Learned (7)
      • Spring (7)
    • 개발서적 (15)
      • 가상 면접 사례로 배우는 대규모 시스템 설계 기초 (1)
      • 오브젝트 - 조영호 (7)
      • 친절한 SQL 튜닝 (7)
    • 회고 (2)
hELLO · Designed By 정상우.
우규이인우윤

Eager To Learn 🌌

👨🏻‍💻 PS/PYTHON

[파이썬 PYTHON · 자바 JAVA] LeetCode【Maximum Product Subarray】

2023. 3. 11. 17:01
 

Maximum Product Subarray - LeetCode

Can you solve this real interview question? Maximum Product Subarray - Given an integer array nums, find a subarray that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer.   Examp

leetcode.com


자바 코드

class Solution {
    public int maxProduct(int[] nums) {
        int [] dp = new int[nums.length];
        int [] maxValue = new int[nums.length];
        int [] minValue = new int[nums.length];

        dp[0] = nums[0];
        maxValue[0] = nums[0];
        minValue[0] = nums[0];
        int ans = nums[0];
        for(int i=1;i<nums.length;i++){
            maxValue[i]=Math.max(Math.max(nums[i],maxValue[i-1]*nums[i]),minValue[i-1]*nums[i]);
            minValue[i]=Math.min(Math.min(nums[i],maxValue[i-1]*nums[i]),minValue[i-1]*nums[i]);

            dp[i] = maxValue[i];
            ans = Math.max(ans,dp[i]);
        }


        return ans;
    }
}

파이썬 코드

class Solution(object):
    def maxProduct(self, nums):
        
        _max = nums[0]
        _min = nums[0]
        ans = nums[0]

        for i in range(1,len(nums)):
            maxResult = max(max(nums[i],_max*nums[i]),_min*nums[i])
            minResult = min(min(nums[i],_max*nums[i]),_min*nums[i])
            
            _max = maxResult
            _min = minResult

            ans = max(ans,maxResult)

        return ans

 

곱셈의 경우 덧셈과 비슷하지만, 음수인 최솟값에 음수가 곱해지면 양수가 되는 상황까지 고려해야한다.

 

따라서 _max 값은 nums[i] 와  _max*nums[i] 와 _min*nums[i] 값 중 가장 큰 값을 기록해야한다.

 

_min값 역시, nums[i] 와 _max*nums[i] 와 _min*nums[i] 값 중 가장 작은 값을 기록해야한다.

 

연산이 끝난 뒤, ans를 최댓값으로 계속 갱신하면 된다.

    '👨🏻‍💻 PS/PYTHON' 카테고리의 다른 글
    • [파이썬 PYTHON] 프로그래머스【무지의 먹방 라이브】
    • [파이썬 PYTHON · 자바 Java] LeetCode【Find Minimum in Rotated Sorted Array】
    • [파이썬 PYTHON · 자바 JAVA] LeetCode【Maximum Subarray】
    • [파이썬 PYTHON · 자바 JAVA] LeetCode【Product of Array Except Self】
    우규이인우윤
    우규이인우윤
    개발자 꿈나무

    티스토리툴바