Given :

  • Profit[n]: a n item array indicating the profit on a day (may be positive or negative)
  • Cost[n]: a n item array indicating the cost of holding a stock on a day (always positive)

Task: Find $1 \leq i \leq j \leq n$ that maximize Total Profit divided by $\sqrt{\text{Total Cost}}$ from day $i$ to day $j$.


  • Does knowing that the total profit over all days = 0 help improve the algorithm?
  • Rather than maximizing the ratio, is it possible to find the maximum profit given a "Budget" (Maximum Cost)
  • Would supposing that the cost remains constant help improve the algorithm?

Attempts to solve:

  • Naive: simply loop through all pairs of $i, j$: ($O(N^2)$)
  • Dynamic programming? - don't know where to start
  • Divide and conquer? - seems applicable but hard to implement
  • Is there an $O(N)$ solution?

Intended Application:

  • I have a sequence of data points and a trendline that estimates the true mean and variance
  • I want to find stretches where the data is on a "hot" or "cold" streak (i.e. where the cumulative excess over the mean is most unexpected compared to the variance.) That's where the square root comes from


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.