Python의 목록에서 각 하위 목록의 최소값 합계를 찾는 프로그램

nums라는 숫자 목록이 있다고 가정합니다. 모든 하위 목록 x에 대해 x의 최소값 합계를 nums로 찾아야 합니다. 답이 너무 크면 결과를 10^9 + 7로 수정합니다.

따라서 입력이 nums =[5, 10, 20, 10, 0]과 같으면 하위 목록이 [[5], [10], [20], [10], [ 0], [5,10], [10,20], [20,10], [10,0], [5,10,20], [10,20,10], [20,10,0] , [5,10,20,10], [10,20,10,0], [5,10,20,10,0]]이고 최소값은 [5, 10, 20, 10, 0, 5, 10, 10, 0, 5, 10, 0, 5, 0, 0]이므로 합계는 90입니다.

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

• ans :=0
• s :=새 목록
• temp_sum :=0
• 숫자 단위의 각 인덱스와 값에 대해 다음을 수행합니다.
  • while s 및 value <=s의 마지막 목록의 인덱스 1에 있는 요소, do
    • temp_sum :=temp_sum - s에 있는 마지막 목록의 인덱스 2에 있는 요소
    • s에서 마지막 요소 삭제
  • s가 비어 있으면
    • s에 세 개의 요소 [인덱스, 값, (인덱스 + 1)*값]이 있는 목록 삽입
  • 그렇지 않으면
    • 세 개의 요소가 있는 목록 삽입 [index, value, (index - s의 마지막 목록의 첫 번째 요소)*value]
  • temp_sum :=temp_sum + s에 있는 마지막 목록의 인덱스 2에 있는 요소
  • ans :=ans + temp_sum
• 모드 반환(10^9 + 7)

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(nums):
   ans = 0
   s = []
   temp_sum = 0
   for index, value in enumerate(nums):
      while s and value <= s[-1][1]:
         temp_sum -= s[-1][2]
         s.pop()
      if not s:
         s.append([index, value, (index + 1) * value])
      else:
         s.append([index, value, (index - s[-1][0]) * value])
      temp_sum += s[-1][2]
      ans += temp_sum
   return ans % (10**9 + 7)

nums = [5, 10, 20, 10, 0]
print(solve(nums))

입력

[5, 10, 20, 10, 0]

출력

90