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$.
Extensions:
- 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
