LeetCode : Maximum Product Subarray (Medium)

4406 ワード
coding test テキストリンク

0. Overview

  • 回答日:2021-06-18
  • プール:30m
  • LeetCode URL : https://leetcode.com/problems/maximum-product-subarray/

    • 1. Problem



    2. Solution

    from typing import List

def maxProduct(nums: List[int]) -> int:
    min_candidates = [n for n in nums]
    max_candidates = [n for n in nums]
    
    for i in range(1, len(nums)) :
        max_candidates[i] = max(min_candidates[i-1] * nums[i], max_candidates[i-1] * nums[i], max_candidates[i])
        min_candidates[i] = min(min_candidates[i-1] * nums[i], max_candidates[i-1] * nums[i], min_candidates[i])
        #print(max_candidates, min_candidates)
    return max(max_candidates)

    3. Review


    前述した「Maximum Subaray」と同様の動的プログラミング手法を用いて問題を解決した.
  • の累積を求める問題とは異なり、累積乗は負の値によって異なる可能性があるため、最大/最小累積乗をiに保持するリストを生成し、比較することで最大累積値を求めることができる.
    • [アルゴリズム/Programmers]行列の加算
    [JavaSE]->{注記と反射04}-->カスタム注記