Solution: Presum + mono Stack
class Solution:
def maxSumMinProduct(self, A: List[int]) -> int:
""" tc O(N) sc O(N)
main idea: assume any A[i] is smallest, extend its max range to get largest presum
1. get left bound: for A[i], within i:0, the first index j so that A[j] < A[i]
2. get right bound
3. cache presum
4. for each A[i], get its best subarry sum; find out gobal best
"""
n = len(A)
presum = [0] * (n+1)
for i in range(n):
presum[i+1] = presum[i] + A[i] # sum(A[left],...A[right]) = presum[right+1]-presum[left]
#print(presum)
left_bound,right_bound = [0]*n, [n-1]*n
# left bound
st1 = []
for i in range(n):
while st1 and A[i] <= A[st1[-1]]:
st1.pop()
if st1: left_bound[i] = st1[-1] + 1 # closest index j that A[j] < A[i]
#else:left_bound[i] = 0 #there is none on the left that smaller than A[i], left_bound[i] = 0
st1.append(i)
# right bound
st2 = []
for i in range(n-1,-1,-1):
while st2 and A[i] <= A[st2[-1]]:
st2.pop()
if st2: right_bound[i] = st2[-1] -1 # st2[-1] is first index j closest to A[i], that A[j] < A[i]
# else right_bound[i] = n -1
st2.append(i)
#print(left_bound,right_bound)
res = 0 # get max
for i in range(n):
left,right = left_bound[i], right_bound[i]
multi = A[i]*(presum[right+1]-presum[left])
res = max(res,multi)
return res % (10**9+7)