# Algorithm question (Similar to Knapsack but with an order, or Stock Buy Sell with a cost parameter)

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