4
\$\begingroup\$

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);
    Integer[] arrRight = Arrays.copyOfRange(arr, split, arr.length);

    // Compute left and right - then return merged solution
    return  merge(left(arrLeft), right(arrRight));
}

public static Integer[] left(Integer[] left) {
    if (left.length == 1) {
        return new Integer[]{left[0], left[0]};
    } else if (left.length == 2) {
        return new Integer[]{Math.min(left[0], left[1]), left[1]};
    } else {
        return splitAndMerge(left);
    }
}

public static Integer[] right(Integer[] right) {
    if (right.length == 1) {
        return new Integer[]{right[0], right[0]};
    } else if (right.length == 2) {
            return new Integer[]{right[0], Math.max(right[1], right[0])};
    } else {
        return splitAndMerge(right);
    }
}

Also it should be noted that Math.max() - Math.min() cannot be used since the the min value could have occurred before the max value, which doesn't make sense given the scenario of selling stocks.

\$\endgroup\$
6
\$\begingroup\$

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 < 1) {
        return 0;
    }

    int maxDiff = 0;
    int localMin = prices[0];
    int localMax = localMin;

    for (int price : prices) {
        if (price > localMax) {
            localMax = price;
            int localDiff = localMax - localMin;
            if (localDiff > maxDiff) {
                maxDiff = localDiff;
            }
        } else if (price < localMin) {
            localMin = localMax = price;
        }
    }

    return maxDiff;
}
\$\endgroup\$
  • \$\begingroup\$ Much simpler algorithm but also slower. You suggested algorithm would be O(n^2) if I am not mistaken. A merge sort algorithm is O(n*log(n)), which is much better. It is true however that the memory usage will be higher in a merge sort style algorithm due to the recursion. Otherwise I like your feedback. Thanks. \$\endgroup\$ – Paul Jun 25 '15 at 6:31
  • 1
    \$\begingroup\$ @Paul janos is describing the same algorithm as maaartinus - it's \$\mathcal{O}(n)\$. \$\endgroup\$ – Veedrac Jun 25 '15 at 7:05
  • 2
    \$\begingroup\$ I clarified the description of my algorithm and also added an implementation. It's \$O(n)\$ time and \$O(1)\$ space. \$\endgroup\$ – janos Jun 25 '15 at 7:25
  • \$\begingroup\$ @Veedrac No, he isn't. He needs no additional array it took me a while to understand it. \$\endgroup\$ – maaartinus Jun 25 '15 at 7:32
  • \$\begingroup\$ Yeah actually I think you're right. That's a very simple way to solve the problem. Thanks. \$\endgroup\$ – Paul Jun 25 '15 at 8:28
3
\$\begingroup\$

This algorithm is new to me. It looks fine except for a few things:

// A few basic tests
System.out.println(stocks(new Integer[]{1, 2, 3, 8, 5}) + " - should be 7");

You should write real tests, e.g., using JUnit. In a separate class you write something like

assertEquals(7, stocks(new Integer[]{1, 2, 3, 8, 5});

and you'll get an exception if it fails. No need to check any output.


Don't use Integer when you don't have to. Ideally, use varargs like

public static int stocks(int... stocks) ...

so that you can write just

assertEquals(7, stocks(1, 2, 3, 8, 5));

Initially, I though you could just manage the indexes instead of copying arrays, but you're also modifying them. So I guess, it's impossible.


Wouldn't this simple algorithm do?

int length = stock.length;

int[] minArray = stock.clone(); // minimum so far
for (int i=1; i<length; ++i) {
    minArray[i] = Math.min(minArray[i-1], stock[i]);
}

int[] maxArray = stock.clone(); // maximum now or later
for (int i=length-2; i>=0; --i) {
    maxArray[i] = Math.max(maxArray[i+1], stock[i]);
}

int result = 0;
for (int i=0; i<length; ++i) {
     result = Math.max(maxArray[i] - minArray[i]);
}

A slightly shortened version of Janos' algorithm

public static int maxProfit(int[] prices) {
    int result = 0;
    int localMin = Integer.MAX_VALUE;
    for (int price : prices) {
        localMin = Math.min(localMin, price);
        result = Math.max(result, price - localMin);
    }
    return result;
}

As Veedrac wrote, there's no need for maxArray. And instead of minArray, the needed value gets computed on the fly.

\$\endgroup\$
  • \$\begingroup\$ I could just send around indexes as I am never modifying the array, just splitting it up. However that would make my code much more complex and harder to read. Also not sure if your algorithm would work. Have you tested it yet? \$\endgroup\$ – Paul Jun 25 '15 at 6:40
  • 1
    \$\begingroup\$ @Paul You could use List.subList to make a view onto a subslice to avoid copying the slices. This would require using a List instead of a primitive array, though. \$\endgroup\$ – Veedrac Jun 25 '15 at 7:14
  • 1
    \$\begingroup\$ @maaartinus You don't need the maxArray - you can just use stock directly. \$\endgroup\$ – Veedrac Jun 25 '15 at 7:24
  • \$\begingroup\$ @Veedrac I guess you're right! The only advantage of using it is the symmetry (which is worth about nothing). \$\endgroup\$ – maaartinus Jun 25 '15 at 7:28
  • \$\begingroup\$ I tried running your shortened version of Janos' algorithm and it's not working for all numbers in my tests given. \$\endgroup\$ – Paul Jun 26 '15 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.