FastPrep
Problem · Array

Count Maximum Profitable Groups 🍑

Learn this problem
● MediumAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

A team of analysts at Amazon needs to analyze the stock prices of Amazon over a period of several months.

A group of consecutively chosen months is said to be maximum profitable if the price in its first or last month is the maximum for the group. More formally, a group of consecutive months [l, r] (1 ≤ l ≤ r ≤ n) is said to be maximum profitable if either:

  • stockPrice[l] = max(stockPrice[l], stockPrice[l + 1], ..., stockPrice[r])
  • or, stockPrice[r] = max(stockPrice[l], stockPrice[l + 1], ..., stockPrice[r])

    • Given prices over n consecutive months, find the number of maximum profitable groups which can be formed. Note that the months chosen must be consecutive, i.e., you must choose a subarray of the given array.

    Function

    countMaximumProfitableGroups(stockPrice: int[]) → long

    Complete the function countMaximumProfitableGroups function in the editor below.

    countMaximumProfitableGroups has the following parameter:

    • int stockPrice[n]: the stock prices

    Returns

    long integer: the number of maximum profitable groups

    🍓 1000 thanks to spike for spike's incredible help! 🥑

    Examples

    Example 1

    stockPrice = [3, 1, 3, 5]return = 10
    The 10 possible groups are [3], [3, 1], [3, 1, 3], [3, 1, 3, 5], [1], [1, 3], [1, 3, 5], [3], [3, 5], [5] In each group, the maximum price is in either the first or last position.

    Example 2

    stockPrice = [1, 5, 2]return = 5
    There are 6 possible groups: [1], [1, 5], [1, 5, 2], [5], [5, 2], [2]. Only [1, 5, 2], is not maximum profitable because its maximum value 5 is not at either end of the group.

    Example 3

    stockPrice = [2, 3, 2]return = 5
    Example 3 illustration
    All 5 groups other than prices [2, 3, 2] are maximum profitable. In [2, 3, 2], the maximum value 3 is neither the first nor the last element. Return 5.

    Constraints

    • 1 ≤ n ≤ 5 * 105
    • 1 ≤ stockPrice[i] ≤ 108

    More Amazon problems

    drafts saved locally
    public long countMaximumProfitableGroups(int[] stockPrice) {
  // write your code here
}
    stockPrice[3, 1, 3, 5]
    expected10
    checking account