Skip to main content

BNY Mellon

BNY Mellon OA 2023 - Stock Prices

A report containing a stock's prices for the past (n) days is provided to a data analyst in the array stockPrice[]. The analyst is required to choose a subsequence of stock prices, called chosenDays. The chosen subsequence of stock prices is balanced if the following condition holds:

stockPrice[chosenDays[i]] - stockPrice[chosenDays[i - 1]] = chosenDays[i] - chosenDays[i - 1] ) for (i > 0).

The score of the chosen subsequence is the sum of stock prices on the chosen days. Find the maximum possible score that can be obtained by choosing an optimally balanced subsequence.

Note:

  • A subsequence is an ordered subset of an array's elements in the same sequential ordering as in the original array.
  • A subsequence of length 1 is always balanced.

Constraints

  • (1 <= n <= 10^5)
  • (1 <= stockPrice[i] <= 10^9)

Example

Consider (n = 5), stockPrice = [1, 5, 3, 7, 8].

Then, the subsequence ([5, 7, 8]) can be chosen. Corresponding chosen days are ([1, 3, 4]) (considering 0-based indexing). Now:

  • stockPrice[3] - stockPrice[1] = 7 - 5 = 2 = 3 - 1
  • stockPrice[4] - stockPrice[3] = 8 - 7 = 1 = 4 - 3

Thus, the subsequence is balanced.

Score = (5 + 7 + 8 = 20), which is the maximum possible. So, the answer is (20).