Determining maximum profit to be made from selling shares
The trick to getting this problem in O(n) is some clever pre-processing.

Examples

Let's take 2 trials:

Trial 1: 1, 2, 3, 4, 5

Trail 2: 5, 4, 3, 2, 1

Obviously best case in Trial 1 is to buy for 4 days and sell on the 5th, for profit of 10.
In Trial 2, there is no profit to be gained, because the price never increases, because there is never a higher maximum down the line.

Trick

This points towards the trick: starting from the end make a note of the maximum encountered thus far.

For Trial 1, the maximums are 5, 5, 5, 5, 5

For Trial 2, the maximums are the same as the prices

Let's try this for a more complex scenario: 10, 1, 9, 2, 8, 3, 7

The corresponding maximums would be: 10, 9, 9, 8, 8, 7, 7

Then, for every day that price &lt; maximum, you should buy. If price = maximum, you should sell, and if price > maximum, wait it out.

Code

This yields the following code, assuming you parse the prices into a non-empty long[] named prices:

long[] maximums = new long[prices.length];
maximums[prices.length - 1] = prices[prices.length - 1];
// fill maximums array, from the end
for (int i = prices.length - 2; i &gt;= 0; i--) {
    if (prices[i] &gt; maximums[i + 1])
        maximums[i] = prices[i];
    else
        maximums[i] = maximums[i + 1];
}

// Trade!
long profit = 0;
for (int i = 0; i &lt; prices.length; i++) {
    if (prices[i] &lt; maximums[i]) {
        // BUY now and SELL at max
        profit += maximums[i] - prices[i]; 
    }
}