PROBLEM LINKS:
DIFFICULTY:
Easy
PREREQUISITES:
- Data Structures
- Pre-Computation
PROBLEM:
Given an array A of n + 1 integers where each array[i] denotes number of houses in each lane i.
Find the maximum houses that can be picked such that the equal houses are picked from each lane and the lanes from which houses are picked are contiguous.
It is not necessary to use all lanes and it is not necessary to pick all houses from a particular lane.
EXPLANATION :
The problem could be simplified as the below equation:
f( l, r) = min(subarray( l, r))*(r - l - 1) where l,r are the left and right bounds and non-inclusive indices of the subarray.
Our goal is to maximise f(l,r).
The above task can be accomplished using stacks.
Below is the code to do so.
```
current_maximum = maximum = l = r = 0;
while(r < n + 1)
{
if( s.empty() || array[s.top()] <= array[r])
{ ss.push(r);
r += 1;
}
else
{
l = s.top();
s.pop();
if( s.empty() )
current_maximum = array[l]*r;
else
current_maximum = array[l]*(r - l - 1);
if( current_maximum > maximum)
maximum = current_maximum;
}
}
while( !s.empty() )
{
l = s.top();
s.pop();
if( s.empty() )
current_maximum = array[l]*r;
else
current_maximum = array[l]*(r - l - 1);
if( current_maximum > maximum)
maximum = current_maximum;
}
```
TIME COMPLEXITY:
O(n+1) as the array is parsed only once
## AUTHOR'S AND TESTER'S SOLUTIONS:
Setter's solution
Tester's solution