Python에서 최대 하위 배열 최소 곱을 찾는 프로그램

<시간/>

배열 num이 있다고 가정하고 num의 비어 있지 않은 각 하위 배열의 최대 최소 곱을 찾아야 합니다. 답은 충분히 클 수 있으므로 모듈로 10^9+7로 반환합니다. 배열의 최소 곱은 배열의 합을 곱한 배열의 최소값과 같습니다. 따라서 배열이 [4,3,6]과 같은 경우(최소값은 3) 최소 곱은 3*(4+3+6) =3*13 =39입니다.

따라서 입력이 nums =[2,3,4,3]과 같으면 결과를 최대화하기 위해 하위 배열 [3,4,3]을 얻을 수 있으므로 출력은 30이 됩니다. 따라서 3*(3+4+ 3) =3*10 =30.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

m :=10^9+7
스택 :=새 스택
rsum :=0, res :=0
숫자 끝에 0 삽입
숫자로 된 각 인덱스 i와 값 v에 대해 수행
- 스택이 비어 있지 않고 nums[스택 상단 인덱스]>=v, do
  동안
  - index, val) :=스택의 맨 위 및 스택에서 팝
  - arrSum:=rsum
  - 스택이 비어 있지 않으면
    - arrSum:=rsum - 스택 맨 위의 값
  - res:=최대 res 및 (nums[index]*arrSum)
- rsum :=rsum + v
- 스택 끝에서 푸시(i, rsum)
res mod 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]