964. Total Squad Strength
A guild lines up its members in a fixed row, and member i has strength strength[i]. Any non-empty block of neighbouring members forms a squad. The power of a squad is the strength of its weakest member multiplied by the total strength of all members in the squad.
Return the sum of the powers of all squads (every distinct position range counts once, even if two ranges contain equal numbers). Because the sum can be huge, return it modulo 1000000007.
Example 1
- Input:
- strength = [4,2,5]
- Output:
- 93
- Explanation:
The six squads score 16, 4, 25, 12, 14 and 22 (weakest times sum), which add up to 93.
Example 2
- Input:
- strength = [7,7]
- Output:
- 196
- Explanation:
Squads [7], [7] and [7,7] score 49, 49 and 98, total 196.
Example 3
- Input:
- strength = [1000000000,1000000000,1]
- Output:
- 178
- Explanation:
The raw total is far larger than the modulus, so the answer is reported modulo 1000000007.
Constraints
- 1 ≤ strength.length ≤ 105
- 1 ≤ strength[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)