Amazon Online Assessment 2021 (OA) - Efficient Harvest
A farmer has a field of crops that he waters using a technique called pivot irrigation, which covers the land in a circular pattern. The field, however, doesn't always yield consistently because of changing conditions; sometimes it gives a lot of produce and other times not so much. The farmer wants to make the most money he can from his harvest, but also needs to be careful not to spend too much on resources. To figure this out, he divides his field into equal parts and calculates how much each section could potentially earn him. This potential profit is determined by comparing the cost of harvesting that segment with how much its produce could sell for.
Imagine this field being divided into, lets say, six parts. The farmer then chooses to invest in two sections that are next to each other, and also the two opposite ones. The estimated profit for each section might look something like [1, 5, 1, 3, 7, -3]. Here's a simple way to visualize this. Consider the first profit to be at the position of 9 in a clock and fill in the rest counterclockwise.
This is where it gets interesting. Look at these scenarios and what happens to the farmer's profit. In the first scenario, the sum of the profit levels from left to right is 1+5+7+3=16. In the second scenario, the same calculation gives us 5+1+7+-3=10. The third scenario ends up with 1+3+-3+1=2. As we can see, the maximum profit that the farmer can earn using this strategy is 16.
Input
k: an integer that denotes half of the needed number of products within the listprofit: an array of integers that denote the profit from investing in each of the products
Output
the maximum profit possible
Examples
Example 1:
Input:
1k = 2 2profit = [1, 5, 1, 3, 7 -3]
Output: 16
Explanation:
The profit levels, from left to right, are 1+5+7+3=16, 5+1+7+-3=10, and 1+3+-3+1=2. The maximum profit is 16.
Example 2:
Input:
1k = 1 2profit = 3 -5
Output: -2
Explanation:
Here k=1 and n=2. The seller will choose 2*k=2 products. In this case, it is the entire list, so overall profit is 3+-5=-2.
Constraints
1 <= k <= n/22 <= n <= 10^5- n is even
0 <= |profit[i]| <= 10^9