資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢最大子陣列最小乘積
假設我們有一個數組 nums，我們需要找到 nums 的每個非空子陣列的最大最小乘積。由於答案可能很大，請將其模 10^9+7 後返回。陣列的最小乘積等於陣列中的最小值乘以陣列的和。例如，如果陣列為 [4,3,6]（最小值為 3），則其最小乘積為 3*(4+3+6) = 3*13 = 39。
因此，如果輸入類似於 nums = [2,3,4,3]，則輸出將為 30，因為我們可以獲得子陣列 [3,4,3] 以最大化結果，因此 3*(3+4+3) = 3*10 = 30。
為了解決這個問題，我們將遵循以下步驟：
m := 10^9+7
stack := 新建一個棧
rsum := 0, res := 0
在 nums 的末尾插入 0
對於 nums 中的每個索引 i 和值 v，執行以下操作：
當棧不為空且棧頂元素對應的 nums 值大於等於 v 時，執行以下操作：
(index, val) := 棧頂元素，並將其從棧中彈出
arrSum:= rsum
如果棧不為空，則：
arrSum:= rsum - 棧頂元素的值
res:= res 和 (nums[index]*arrSum) 中的最大值
rsum := rsum + v
將 (i, rsum) 推入棧的末尾
返回 res 模 m
示例
讓我們看看以下實現以更好地理解：
def solve(nums):
m = int(1e9+7)
stack = []
rsum = 0
res = 0
nums.append(0)
for i, v in enumerate(nums):
while stack and nums[stack[-1][0]] >= v:
index, _ = stack.pop()
arrSum=rsum
if stack:
arrSum=rsum-stack[-1][1]
res=max(res, nums[index]*arrSum)
rsum += v
stack.append((i, rsum))
return res % m
nums = [2,3,4,3]
print(solve(nums))輸入
[2,3,4,3]
輸出
30
更新於: 2021年10月8日
221 次檢視
廣告