Maximum Demolition Profit
A demolition crew is clearing a row of buildings. Each building has a net value that may be positive or negative.
The crew can demolish buildings only from the ends of the remaining row. Determine the maximum total value it can collect.
Demolition Operations
While more than two buildings remain, the crew must perform exactly one of these operations:
- Demolish the first two buildings.
- Demolish the last two buildings.
- Demolish the first and last buildings.
Rules
- The values of both demolished buildings are added to the total.
- Demolition continues until only one or two buildings remain.
- Buildings remaining at the end do not contribute to the total.
- The relative order of the remaining buildings does not change.
Maximum Demolition Profit
Implement the following method:
int maximumDemolitionProfit(List<Integer> buildingValues)
buildingValues contains the net value of each building in order.- The method returns the maximum total value collected from demolished buildings.
Constraints
1 ≤ buildingValues.size() ≤ 100,000-10,000 ≤ buildingValues.get(i) ≤ 10,000 for every 0 ≤ i < buildingValues.size().
Examples
Example 1
maximumDemolitionProfit( buildingValues = List.of(7, 4, -2, 9, 3) )
Output: 23
Demolish the first two buildings to collect 7 + 4 = 11. Then demolish the last two buildings to collect 9 + 3 = 12. The total collected value is 23.
Example 2
maximumDemolitionProfit( buildingValues = List.of(5, -4, 8, 1, -2, 6) )
Output: 15
First demolish the buildings with values 5 and -4. Then demolish the two end buildings with values 8 and 6. The collected value is 1 + 14 = 15.
Example 3
maximumDemolitionProfit( buildingValues = List.of(-6, -1, -4) )
Output: -5
Demolishing the last two buildings collects -1 + -4 = -5, which is the maximum possible total.
Example 4
maximumDemolitionProfit( buildingValues = List.of(12, -8) )
Output: 0
Only two buildings are present, so no demolition operation is performed.