Amazon Online Assessment 2021 (OA) - Max Profit

Imagine you're playing a video game where you're an online store owner. You've got a cool wheel that represents the stuff you can sell, kind of like a colorful pie chart. Your mission is to pick the best slices to earn the most coins for the next three levels (or months).

Here's the catch: the game's market is as unpredictable as the weather in April—sometimes sunny, sometimes rainy. Your goal is to make as many coins as possible without spending them all in one place. You've got to invest your coins in slices that are side-by-side, and to make things interesting, also in the slices directly across from them on the wheel.

Let's say the wheel has six slices (like six items to choose from). If you decide to go for two slices that are buddies and their two opposite pals, the game calls this a "k=2" move. Each slice has a number that tells you how many coins you could earn, like a fortune prediction.

So, imagine your wheel has these numbers: [1, 5, 1, 3, 7, -3]. You've got to think like a pro and figure out which slices will give you the highest score. The game shows you different combos like a puzzle. One combo gives you 1+5+7+3=16 coins, another gives you 5+1+7-3=10 coins, and a not-so-great one gives you 1+3-3+1=2 coins.

After checking out your options, you see that the first combo with 16 coins is the jackpot. That's the best move to level up your store and win the game. This part of the game is like a fun mini-challenge, where you've got to use your math skills to pick the winning slices and beat the market!

Relevant Amazon OA Problems:

Input

k: an integer that denotes half of the needed number of products within the list
profit: an array of integers that denote the profit from investing in each of the products

Output

the maximum profit possible

Examples

Example 1:

Input:

k = 2
profit = [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:

k = 1
profit = 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/2
2 <= n <= 10^5
n is even
0 <= |profit[i]| <= 10^9