#2281

Sum of Total Strength of Wizards

international master · 2000 · lc hard +32 · failed · 29.2% accepted · 1,267 likes · top 7%

Description

You lead an army of n wizards.

You are given a 0-indexed integer array strength where strength[i] is the strength of wizard i. For any contiguous subarray of wizards, the group's total strength is the minimum strength in the group multiplied by the sum of all strengths in the group.

Return the sum of total strengths over all contiguous groups, modulo 10⁹ + 7.

Example 1:

Input: strength = [1,3,1,2]

Output: 44

Explanation: The following are all the contiguous groups of wizards:

- [1] from [1,3,1,2] has a total strength of min([1]) * sum([1]) = 1 * 1 = 1

- [3] from [1,3,1,2] has a total strength of min([3]) * sum([3]) = 3 * 3 = 9

- [1] from [1,3,1,2] has a total strength of min([1]) * sum([1]) = 1 * 1 = 1

- [2] from [1,3,1,2] has a total strength of min([2]) * sum([2]) = 2 * 2 = 4

- [1,3] from [1,3,1,2] has a total strength of min([1,3]) * sum([1,3]) = 1 * 4 = 4

- [3,1] from [1,3,1,2] has a total strength of min([3,1]) * sum([3,1]) = 1 * 4 = 4

- [1,2] from [1,3,1,2] has a total strength of min([1,2]) * sum([1,2]) = 1 * 3 = 3

- [1,3,1] from [1,3,1,2] has a total strength of min([1,3,1]) * sum([1,3,1]) = 1 * 5 = 5

- [3,1,2] from [1,3,1,2] has a total strength of min([3,1,2]) * sum([3,1,2]) = 1 * 6 = 6

- [1,3,1,2] from [1,3,1,2] has a total strength of min([1,3,1,2]) * sum([1,3,1,2]) = 1 * 7 = 7

The sum of all the total strengths is 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44.

Example 2:

Input: strength = [5,4,6]

Output: 213

Explanation: The following are all the contiguous groups of wizards:

- [5] from [5,4,6] has a total strength of min([5]) * sum([5]) = 5 * 5 = 25

- [4] from [5,4,6] has a total strength of min([4]) * sum([4]) = 4 * 4 = 16

- [6] from [5,4,6] has a total strength of min([6]) * sum([6]) = 6 * 6 = 36

- [5,4] from [5,4,6] has a total strength of min([5,4]) * sum([5,4]) = 4 * 9 = 36

- [4,6] from [5,4,6] has a total strength of min([4,6]) * sum([4,6]) = 4 * 10 = 40

- [5,4,6] from [5,4,6] has a total strength of min([5,4,6]) * sum([5,4,6]) = 4 * 15 = 60

The sum of all the total strengths is 25 + 16 + 36 + 36 + 40 + 60 = 213.

Code

1

2

3

class Solution:
    def totalStrength(self, strength: List[int]) -> int:

class Solution:
    def totalStrength(self, strength: List[int]) -> int: