一道奇怪的題目，用單調棧。
遍歷array中的元素，然后對比棧頂?shù)臄?shù)字，
如果比棧頂?shù)拇?#xff0c;入棧。

如果比棧頂?shù)男?#xff0c;棧頂元素出棧。
此時，被從棧頂元素開始往回看，因為是單調上升的單調棧，其之后的元素一定小于棧頂這個元素。于是，每次彈出的元素，都是原本棧頂元素對應的位置往回遍歷到當前棧頂元素中的最小值。于是，我們可以更新此時的susbarry的計算值。我們還需要注意的是，每次遍歷到的值入棧，我們都入棧這個值，以及這個值往回看，作為最小值可以到達的最左側的位置。也就是這個值為最小值的subarray的最左側起始位置。

class Solution:def maxSumMinProduct(self, nums: List[int]) -> int:Mod = 10**9 + 7prefixsum = [0 for _ in range(len(nums) + 1)]for i in range(len(nums)):prefixsum[i+1] = prefixsum[i] + nums[i]res = float('-inf')stack = []# [a, b, c, d, e]# [0,sa,sb,sc,sd,se]for i in range(len(nums)):start = iwhile stack and stack[-1][1] > nums[i]:start, value = stack.pop()res = max(res, value*(prefixsum[i] - prefixsum[start]))stack.append((start, nums[i]))while stack:start, value = stack.pop()res = max(res, value*(prefixsum[len(nums)] - prefixsum[start]))return res%Mod

總結

以上是生活随笔為你收集整理的Leetcode 1856. Maximum Subarray Min-Product [Python]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。