See the original problem on HackerRank.
Solutions
Jotting down a brute force solution is easy but inefficient. The problem can be solved efficiently only by implementing a strategy to skip unnecessary checks.
One solution uses two stacks and two support arrays:
 stack
memoryL
keeps track of the latest elements that are smaller than the current one (from left to right)
 stack
memoryR
keeps track of the latest elements that are smaller than the current one (from right to left)
 array
left
contains the values of \(Left\)
 array
right
contains the values of \(Right\)
Think about how to construct the left
array.
For example:
We read 7
and, since it’s the first element, left[0] = 0
. We push it on to the stack.
Then we read 6
and we check it agains the top of the stack. 7
is there! It means that the leftmost element bigger than 6
is 7
(we actually use the stacks to keep track of the indexes but the point should be clear).
Thus, left[1] = 7
. We push 6
on to the stack.
The next element is 8
. We check it against the top of the stack but 6
is lower. We pop 6
from the stack. We check against the stack and 7
is there. It’s lower than 8
too. We pop it too. The stack is not empty. This means that left[2] = 0
.
We push 8
on to the stack.
The next element is 5
that is lower than the top of the stack so we have left[3] = 8
. We push 5
on to the stack.
We read 7
that is greater than the top of the stack (5
). We pop the latter out. We find 8
that is greater than 8
. Even left[4]
is 8
.
We push 7
on to the stack.
Did you get it? left[5] = 0
and left[6] = 9
.
right
is constructed similarly but…backwards!
Finally, we calculate the product between left
and `right.
Here is a C++ implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

int N;
cin >> N;
vector<int> arr(N), left(N), right(N);
copy_n(istream_iterator<int>(cin), N, begin(arr));
stack<int> memoryL, memoryR;
auto i=0; auto j=N1;
for (; i<N; ++i, j)
{
while (!memoryL.empty() && arr[memoryL.top()1] <= arr[i])
memoryL.pop();
while (!memoryR.empty() && arr[memoryR.top()1] <= arr[j])
memoryR.pop();
if (memoryR.empty())
right[j] = 0;
else
right[j] = memoryR.top();
if (memoryL.empty())
left[i] = 0;
else
left[i] = memoryL.top();
memoryL.push(i+1);
memoryR.push(j+1);
}
auto maxIndexProd = 0ll;
for (i=0; i<N; ++i)
{
maxIndexProd = max(maxIndexProd, static_cast<long long>(left[i])*right[i]);
}
cout << maxIndexProd << endl;

Calculating the product can be replaced with inner_product
(or trasform_reduce
):
1
2
3

auto maxIndexProd = inner_product(begin(left), end(left), begin(right), 0ll,
[](auto l, auto r){ return std::max(l, r); },
[](auto l, auto r){ return (long long)l*r; });

A similar approach in Rust.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

fn solve(arr: &[usize]) > usize {
let n = arr.len();
// contains the values of Left
let mut left: Vec<usize> = vec![0; n];
// contains the values of Right
let mut right: Vec<usize> = vec![0; n];
// keeps track of the latest elements that are smaller than the current one
// (from left to right)
let mut left_stack: Vec<usize> = Vec::new();
// keeps track of the latest elements that are smaller than the current one
// (from right to left)
let mut right_stack: Vec<usize> = Vec::new();
let mut i = 0;
let mut j = n  1;
let remove_smaller_elements = stack: &mut Vec<usize>, index: usize {
while let Some(&x) = stack.last() {
if arr[x  1] <= arr[index] {
stack.pop();
} else {
break;
}
}
};
while i < n {
remove_smaller_elements(&mut left_stack, i);
remove_smaller_elements(&mut right_stack, j);
right[j] = right_stack.last().copied().unwrap_or_default();
left[i] = left_stack.last().copied().unwrap_or_default();
left_stack.push(i + 1);
right_stack.push(j + 1);
i = i.saturating_add(1);
j = j.saturating_sub(1);
}
left.iter()
.zip(right.iter())
.map((l, r) l * r)
.max()
.unwrap_or(0)
}

Another approach  more convoluted  uses three support arrays:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

const int Domain = 100000;
int a[Domain]{}, s[Domain]{}, l[Domain]{};
int N, m = 0;
cin >> N;
auto ans = 0ll;
for (auto i = 0; i < N; i++)
{
cin >> a[i];
while (m && a[s[m1]] < a[i])
ans = max(ans, l[s[m]]*(long long)(i+1));
while (m && a[s[m1]] == a[i])
m;
l[i] = m ? s[m1]+1 : 0;
s[m++] = i;
}
cout << ans;

Left to the reader, another accepted solution consists in using an ordered data structure (e.g. treebased set).