The stocks problem - find the biggest profit that can be made

The Stocks Problem: Given an array of n integers representing the
price of a stock over the course of n days, determine the maximum
profit you can make if you can buy and sell exactly 1 stock over these
n days.

My solution is using the same approach as the merge sort algorithm. It is implemented using Java. I am looking for harsh feedback including advice on function names, layout, formating etc..

```
public static void main (String[] args) {
// A few basic tests
System.out.println(stocks(new Integer[]{1, 2, 3, 8, 5}) + " - should be 7");
System.out.println(stocks(new Integer[]{100, -1000, 3, 8, -1, 9, -2000}) + " - should be 1009");
System.out.println(stocks(new Integer[]{-3000, -1000, 3, 8, -1, 9, 2000}) + " - should be 5000");
System.out.println(stocks(new Integer[]{-3000, 1001, 5001, -2000, 2000, 5000}) + " - should be 8001");
System.out.println(stocks(new Integer[]{-3000, 1001, 5000, -2000, 2000, 5001}) + " - should be 8001");
System.out.println(stocks(new Integer[]{-3000, 1001, 4000, -2000, 2000, 5000}) + " - should be 8000");
}

public static int stocks(Integer[] stocks) {
// Calculate max and minimum value
Integer[] maxmin = splitAndMerge(stocks);

// Biggest stock is difference between max and min value (considering time)
return maxmin[1] - maxmin[0];
}

public static Integer[] merge(Integer[] leftMinMax, Integer[] rightMinMax) {
// Finding the biggest min max combination between the 4 values.
if (rightMinMax[1] - Math.min(rightMinMax[0], leftMinMax[0])
> Math.max(rightMinMax[1], leftMinMax[1]) - leftMinMax[0]) {
return new Integer[] {Math.min(rightMinMax[0], leftMinMax[0]), rightMinMax[1]};
} else {
return new Integer[] {leftMinMax[0], Math.max(rightMinMax[1], leftMinMax[1])};
}
}

public static Integer[] splitAndMerge(Integer[] arr) {
// Split array into two parts
int split = arr.length / 2;
Integer[] arrLeft = Arrays.copyOfRange(arr, 0, split)

This implementation is very inefficient due to creating a lot of arrays. Even worse is that the arrays are of type Integer[] instead of int[] which would be lighter.

A much simpler algorithm is possible:

• iterate over the prices

• keep track of the max difference seen so far, and the local minimum and maximum

• if the current price is bigger than the local max

• update the local max

• if the difference from the local minimum is bigger than the max difference seen so far, then update the max difference = the best time to sell so far

• if the current price is less than the local minimum then reset the local min and max

• the maximum profit is the maximum difference at the end of the iteration

It's nice that you added some test cases, but it would be a lot better to turn those into proper junit test cases.

You missed some interesting corner cases:

• decreasing sequence, for example: 5, 1

• degenerate input: empty array or single element

Negative values as stock prices in the test cases seem strange and a bit confusing.

"stocks" is a poor name for a function that returns an integer. Plural names imply some sort of collection. The number returned is the maximum profit you can make. So for example calculateMaxProfits would be more appropriate.

Suggested implementation

Applying the suggestions above,
here's a solution that's \$O(n)\$ time and \$O(1)\$ space.

public int maxProfit(int[] prices) {
    if (prices.length  localMax) {
            localMax = price;
            int localDiff = localMax - localMin;
            if (localDiff > maxDiff) {
                maxDiff = localDiff;
            }
        } else if (price < localMin) {
            localMin = localMax = price;
        }
    }

    return maxDiff;
}

StackExchange Code Review Q#94620, answer score: 6