Amazon Online Assessment question

Round 1

Questions: The developers at Amazon SQS are working on optimizing the message queue algorithm. There are n events to be sent through a queue, and the size of the th event payload is denoted by payload[i]. The queue performs more efficiently if a subset of the events can be selected and rearranged into a new array called optimizedPayload, which satisfies the following conditions, regardless of the original order of the elements:

1. The first part of optimizedPayload forms an increasing sequence: optimizedPayload[1] < optimizedPayload[2] < ... < optimizedPayload[i -1] < optimizedPayload[i] (Increasing order from the start to i).

2. The second part of optimizedPayload forms a decreasing sequence: optimizedPayload[i] > optimizedPayload[i + 1] > ... > optimizedPayload[j-1] > optimizedPayload[j] (Decreasing order from i to j).

3. The third part of optimizedPayload forms an increasing sequence: optimizedPayload[j] < optimizedPayload[j + 1] < ... < optimizedPayload[n] (Increasing order from j to the end).

The order of elements in optimizedPayload can be rearranged to meet these conditions, meaning the original order of the payload array does not matter when forming the subset.

The task is to determine the maximum number of events that can be selected and rearranged to form optimizedPayload that satisfies the Increasing-decreasing-increasing configuration.

For example:

payload: [1, 3, 5, 4, 2, 6, 8, 7, 9]

Answer is 9 because of increasing part 1, 3, 5; decreasing part 5, 4, 2; increasing part 2, 6, 7, 8, 9.