Luís Ramalho bio photo

Luís Ramalho

Developer & Entrepreneur

Twitter LinkedIn Github Stackoverflow

MaxProfit is a problem where one must compute the maximum possible earnings given a log of stock prices. Note that before attempting this problem, you should read the material on maximum slice.

Our goal is to basically compute the maximum profit that ends in a given position. Thus, if we assume that the maximum profit that ends in a position i equals maxProfit then the maximum slice ending in position i + 1 is going to be max(0, maxProfit + (ai - ai - 1)).

int maxProfit = 0;
int maxSlice = 0;

for (int i = 1; i < a.length; i++) {
    maxProfit = Math.max(0, maxProfit + (a[i] - a[i - 1]));
    maxSlice = Math.max(maxSlice, maxProfit);
}

if (maxSlice < 0) {
    maxSlice = 0;
}

return maxSlice;

The full solution can be found here.