Problem · Stack

Sum of System Vulnerability

HardAmazonNEW GRADOA
See Amazon hiring insights

An application at Amazon is deployed on n servers connected linearly. The vulnerability of the ith server is given by vulnerability[i]. The system vulnerability of a contiguous segment of servers is a subsegment defined as the product of the number of servers and the maximum vulnerability of the servers in the segment.

Given the array vulnerability, find the sum of the system vulnerability of all the segments of the servers. Since the answer can be large, report it modulo 10^9 + 7.

ᥫ᭡。spike carries again! ฅ՞•ﻌ•՞ฅ

Examples
01 · Example 1
vulnerability = [3, 2, 3]
return = 29
Example 1 illustration
The sum of all system vulnerabilities is 3 + 6 + 9 + 2 + 6 + 3 = 29.
02 · Example 2
vulnerability = [4, 2, 1, 2]
return = 59
For each subsegment, calculate the number of servers, maximum vulnerability, and system vulnerability: Subsegment Number of servers Maximum Vulnerability System Vulnerability [4] 1 4 1 * 4 = 4 [4, 2] 2 4 2 * 4 = 8 [4, 2, 1] 3 4 3 * 4 = 12 [4, 2, 1, 2] 4 4 4 * 4 = 16 [2] 1 2 1 * 2 = 2 [2, 1] 2 2 2 * 2 = 4 [2, 1, 2] 3 2 3 * 2 = 6 [1] 1 1 1 * 1 = 1 [1, 2] 2 2 2 * 2 = 4 [2] 1 2 1 * 2 = 2 Sum of system vulnerabilities = 4 + 8 + 12 + 16 + 2 + 4 + 6 + 1 + 4 + 2 = 59
03 · Example 3
vulnerability = [4, 4]
return = 16
For each subsegment, calculate the number of servers, maximum vulnerability, and system vulnerability: Subsegment Number of servers Maximum Vulnerability System Vulnerability [4] 1 4 1 * 4 = 4 [4, 4] 2 4 2 * 4 = 8 [4] 1 4 1 * 4 = 4 Sum of system vulnerabilities = 4 + 8 + 4 = 16
Constraints
  • The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of servers.
  • The next n lines contain integers vulnerability[i] (1 ≤ vulnerability[i] ≤ 10^5) — the vulnerability of each server.
  • More Amazon problems
    drafts saved locally
    public int sumOfSystemVulnerability(int[] vulnerability) {
      // write your code here
    }
    
    vulnerability[3, 2, 3]
    expected29
    sign in to submit