Editorialist: Raj Shah
DIFFICULTY:
EASY
PREREQUISITES:
Basic Logical Math, Subarray Properties
PROBLEM:
You are given a sequence of integers. You are allowed to pick some contiguous segment of this sequence (that is, a segment without any gaps), and multiply the length of this segment by the minimum number in the segment.We have to find the maximum value that we can generate in this manner.
For example, suppose the given sequence is 7, 2, 8, 10. If you pick the entire sequence, the length is 4 and the minimum number is 2, so the product is 8.If you pick the segment 8, 10, the length is 2 and the minimum number is 8, so the product is 16. This one is the maximum value you can generate for this sequence.Note that you cannot pick 7, 8, 10, since it is not a contiguous segment.
QUICK EXPLANATION:
For every number in the array, keep going left till you find a number smaller than itself, similarly go to the right. (Do not take the smaller values).
This is the range in which the number is the minimum. Let L = left endpoint of the range and R= right endpoint.Length will be equal to R - L + 1. Multiply this length by the number, since that’s the largest answer we can obtain where this particular number is minimum.
The final answer is the maximum of all such numbers.
SOLUTIONS:
- 5,14,8,7,6,10,10,4,2,5,30
| Number | Left | Right | Length | Answer |
|---|---|---|---|---|
| 5 | 1 | 7 | 7 | 35 |
| 14 | 2 | 2 | 1 | 14 |
| 8 | 1 | 3 | 3 | 24 |
| 7 | 2 | 4 | 3 | 21 |
| 6 | 2 | 7 | 6 | 36 |
| 10 | 6 | 7 | 2 | 20 |
| 10 | 6 | 7 | 2 | 20 |
| 4 | 1 | 9 | 9 | 36 |
| 2 | 1 | 11 | 11 | 22 |
| 5 | 10 | 11 | 2 | 10 |
| 30 | 11 | 11 | 1 | 30 |
Final Answer = 36
- 24,22,16,18,6,7,17,16,5,20,8,19,16
| Number | Left | Right | Length | Answer |
|---|---|---|---|---|
| 24 | 1 | 1 | 1 | 24 |
| 22 | 1 | 2 | 2 | 44 |
| 16 | 1 | 4 | 4 | 64 |
| 18 | 4 | 4 | 1 | 18 |
| 6 | 1 | 8 | 8 | 48 |
| 7 | 6 | 8 | 3 | 21 |
| 17 | 7 | 7 | 1 | 17 |
| 16 | 7 | 8 | 2 | 32 |
| 5 | 1 | 13 | 13 | 65 |
| 20 | 10 | 10 | 1 | 20 |
| 8 | 10 | 13 | 4 | 32 |
| 19 | 12 | 12 | 1 | 19 |
| 16 | 12 | 13 | 2 | 32 |
Final Answer = 65
- 15,30,23,1,47,23,3,8,9,10,19,21,13,5,4
| Number | Left | Right | Length | Answer |
|---|---|---|---|---|
| 15 | 1 | 3 | 3 | 45 |
| 30 | 2 | 2 | 1 | 30 |
| 23 | 2 | 3 | 2 | 46 |
| 1 | 1 | 15 | 15 | 15 |
| 47 | 5 | 5 | 1 | 47 |
| 23 | 5 | 6 | 2 | 46 |
| 3 | 5 | 15 | 11 | 33 |
| 8 | 8 | 13 | 6 | 48 |
| 9 | 9 | 13 | 5 | 45 |
| 10 | 10 | 13 | 4 | 40 |
| 19 | 11 | 12 | 2 | 38 |
| 21 | 12 | 12 | 1 | 21 |
| 13 | 11 | 13 | 3 | 39 |
| 5 | 8 | 14 | 7 | 35 |
| 4 | 5 | 15 | 11 | 44 |
Final Answer = 48