IFS Labs is in the South of France, on a mission to source a rare type of ingredient required for their Turkish Delight confectionary. They stumble upon a rather peculiar market where all the shops are arranged in a straight line, stretching as far as the eye can see. Each shop sells a limited amount of this ingredient and each shop stocks different amounts of it.
There is a catch though, the competition in this market is so intense that if you buy from one shop, the other two vendors on either side of it will down right refuse to sell you their goods.
The challenge then, if you choose to accept, is to find which shops can be visited to maximize the amount of goods that can be purchased.
1. Money isn’t a problem
2. The ingredient is measured in gallons and is always positive
3. IFS Labs has infinite amounts of storage capacity
4. The quality of the ingredient sold at each shop is the same
Sample Data Set
"id" : ID,
"generatedOn" : DATE,
"data" : [ 6, 2, 3, 12, 4 ]
Assuming the index of the above “data” array identifies the shop:
It can be interpreted as
Buying from “Shop 0” means that 6 gallons can be purchased but “Shop 1” will not sell you their goods. Likewise buying from “Shop 2” means 3 gallons can be purchased but neither “Shop 1” nor “Shop 3” will sell you their goods. Our goal is to maximize the amount that can be bought so the optimal solution would be to visit “Shop 0” and “Shop 3” which gives you a total of 18 gallons of this precious ingredient.
The expected output is a text file in JSON format.
"answer" : [ 0 , 3 ]