ORIGINAL CODING QUESTION

Sum of all segment minimums

For every nonempty contiguous segment take its minimum. Return the sum of these minimums.

Open practice workspace

Original exercise · hard. Editorial role relevance does not imply a company has asked this question.

Input and output

n, then n integer values. Print one integer as described.

Constraints

1 ≤ n ≤ 200; -100 ≤ value ≤ 100. Inputs contain exactly the stated values.

Example 1

Input

3 3 1 2

Output

Minimums 3,1,2,1,1,1 sum to 9.

Example 2

Input

2 -1 -1

Output

-3

All three segments contribute -1.

Explain your approach

Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?

Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.

Hint 1

Count how many segments select each position as their minimum.

Hint 2

Previous/next smaller boundaries define its contribution.

Hint 3

Use a consistent strict/non-strict convention for equal values to avoid double counting.

Practice this question

Save your work privately, explain decisions and return to your revision queue.

Open practice workspace Browse the question library →