[Challenge] Maximize Stock Trading Profit

Using Java, this is my solution to the basic problem.

https://repl.it/I0el/2

I tried to get around the solution of nested for loops by essentially cramming everything together in one loop.

1 Like

Here’s my solution in C#. I’m new to programming and this is my first challenge, so this probably isn’t the best solution. Let me know if there are any improvements I can make.

namespace CodeChallenge8Basic
{
    class Program
    {

        static int[] arrayOfPrices = new int[] { 17, 11, 60, 25, 150, 75, 31, 120 };
        static int bestValue = 0;
        static int bestBuyDate;
        static int bestSellDate;

        static void Main(string[] args)
        {
            bestDays();

            Console.WriteLine("{0} is the best day to buy. {1} is the best day to sell. {2} is the best value.",
                bestBuyDate,
                bestSellDate,
                bestValue);

            Console.ReadLine();
        }

        public static void bestDays()
        {
            // Initialize a counter so I can keep track of what item I'm on
            // I do this so I don't cycle through nonsensical options like 
            // purchasing on day 2 and selling on day 1
            int counter = 0;

            // Run a for-loop that cycles through each item in the array. 
            // Each cycle of this for-loop will have a nested for-loop that compares
            // the current item to every SUBSEQUENT item. Hence the counter.
            foreach (var item in arrayOfPrices)
            { 
                for (int i = 0; i < arrayOfPrices.Length - (counter + 1); i++)
                {
                    if (arrayOfPrices[i+1] - arrayOfPrices[counter] > bestValue)
                    {
                        bestValue = arrayOfPrices[i + 1] - arrayOfPrices[counter];
                        bestBuyDate = counter;
                        bestSellDate = i + 1;
                    }
                }
                counter++;
            }
        }
    }
}
1 Like

Basic Challenge:

Simply: use a double for loop to evaluate applicable pairs (cannot evaluate a pair that evaluates against a day that is before or equal to it). Get the pair with the largest gain.

If we run into day pairs that evaluate as having the same gains, we will then evaluate which day pair made the gains in less time. If both the gains and the time taken to make those gains are both equal, we will use the pair closest to day 0. Thus, our gains are evaluated as greater, faster, sooner.

If no day pairs evaluate to any gains, “noTrade” will be returned.

https://repl.it/I0jM/6

2 Likes

The number of days in your list should be 7 instead of 8.

Intermediate difficulty:

Go through each element, evaluating as follows:

  • is the next element a higher value? if so, set the current element as the start day.
  • now, go through the next elements and stop on the day before values start to drop. this is your end day.
  • place the day pair into the array.
  • start evaluating again at the day after the last end day.
  • return the array. The array will return empty if:
    • not enough days were provided.
    • no gains were possible.

The way the for/if/while arguments evaluate:

  • days in array will always be different (following rule about 1 buy/sell per day)
  • if prices are the same for days in a row before buying, the buy day will be delayed (delay payables). You will be holding on to your money until you need to use it.
  • if prices are the same for days in a row before selling, the sell day will be the soonest sell day possible (expedite receivables). You will receive your money sooner so you can use it to buy again.

https://repl.it/I0n6/8

1 Like

Where does it say this? I am using the array that was provided in the challenge.

Hello,

I have a problem with the timing. Am I at day 8 and should predict the future (for which the dataset would be too small) or am I at day 0 and moving towards the future with the array? So on my day two the stock’s price is also arr[1]? Or am I on day 9 sitting in my living room typing a few lines of code that sort the stock price of last week showing me when I should have bought and sold my stock?

Yeah I know I have a complicated mind :slight_smile:

Okay, now I’ve got this! I was presuming it to be the details of a week (7 days), but the array gives details of a random figure of 8 days (0 to 7)…sorry for the error, I’ve understood it now.

So here is my go at the basic difficulty. I tried doing it a bit differently, try it here: https://repl.it/I1G7

def best_days(lst):
    highest = lst.index(max(lst))
    lowest = lst.index(min(lst))

    cash = lst[highest] - min(lst[0:highest])

    if max(lst[lowest:]) - lst[lowest] > cash:
        return lowest, lst.index(max(lst[lowest:]))

    return lst.index(min(lst[0:highest])), highest

Basically, you find the smallest value and calculate how much you would make if you buy it and sell for the biggest value after it.

The, just to check, you find the biggest value and calculate how much you would make if you sold now and bought for the smallest value before it.

In the example test array, these are the same, but that’s not always the case.

Basic difficulty in Python 2

The array is traversed, holding the parameters for best achievable transaction in a set of variables. The parameters are modified when a new low price is reached, or new max gain.

https://repl.it/I1VX/20

Here is my solution for the Basic Difficulty Challenge writed on JS (ES6), suggestions and possible improvements are welcome

var bestDays = (arr) => {
  var currentProfit, maxProfit = 0, bDayB, bDayS;
  for (var i = 0; i < arr.length; i++) {
    for (var j = i + 1; j < arr.length; j++)
      if (arr[j] - arr[i] > maxProfit) {
        maxProfit = arr[j] - arr[i];
        bDayB = i;
        bDayS = j;
      }
    arr.shift();
  }
  console.log(`Max. Profit: ${maxProfit}, Buy On Day ${bDayB} and Sell On Day ${bDayS}`);
}

Hi swky! You might want to consider what happens in your inner for-loop when i = 2, for example :slight_smile: you want it to start from j = i + 1, or else you might be selling before you buy

You are looking back at last week’s and figuring out what you should have done.

1 Like

Intermediate challenge (JavaScript)
After viewing some of the other works and realizing the existence of the map method and the incredibly code-efficient way of applying it here, I noticed my code is rather extensive. On the plus-side, it’s a bit more readable to novice coders :slight_smile:

https://repl.it/I05F/8

Uncomment the console log commands for a better view of the step-by-step process

EDIT: only just now realized the output had to specify the days, not the values. A quick fix solved that, though :slight_smile:

Managed with both basic and intermediate challenges without any clue about relevant algorithms. Needless to say, efficiency is absolutely disgusting, but I’m happy I’ve done it myself.

Basic level:
Traverse the array, pairing the current value with the highest value found to the right of it. Look for the pair that produces the biggest difference.

Time is O(n^2 / 2). The maxprofit is initiated silly to comply with the “market crash” scenario. Alternatively it could be foolproofed: maxprofit = min(stocks) - max(stocks) at the additional cost of O(2n).

def bestDays_easy(stocks):
    maxprofit = -999999
    
    for day in range(0, len(stocks)-1):
        price = stocks[day]
        futmax = max(stocks[day+1:])
        if futmax - price > maxprofit:
            buyday  = day
            sellday = stocks[day+1:].index(futmax) + day+1
            maxprofit = futmax - price
            
    return buyday, sellday

Intermediate level:
Had to prop myself up here with combinations from the standard library. First I produce an array of unique combinations of elements from the input array, grouped in tuples of mod2 length (to enable complete buy-and-sell cycles). Then I calculate the sum of each tuple, switching the sign of every other (odd-indexed) element to reflect buying shares. The tuple producing the highest sum is converted to 2D array as stipulated.

def bestDays(stocks):
    from itertools import combinations

    maxprofit = -1 * sum(stocks)
    combs = set([comb for i in range(2, len(stocks), 2) for comb in
                combinations(range(len(stocks)), i)])

    for path in combs:
        profit = sum(stocks[i]*(-1)**(path.index(i)+1) for i in path)
        if profit > maxprofit:
            maxprofit = profit
            bestpath = path

    return [[bestpath[i],bestpath[i+1]] for i in range(len(bestpath)) if i%2==0]

Efficiency is nasty, input arrays over 25 elements need minutes on my box to compute :hushed:
Both functions however produce correct output in the “market crash” scenario:

>>> bestDays_easy([12, 10, 8, 6, 4, 3, 1])
(4, 5)
>>> bestDays([12, 10, 8, 6, 4, 3, 1])
[[4, 5]]

reidswan101’s elegant solutions need a fix here.

repl.it link - not embedding as this page becomes a nightmare to navigate when everyone does it.

1 Like

You’re right, but why should we change the start value of j instead of his end value? I think that the correct value would be j < arr.length - i.

Please correct me if I am wrong and thanks for your comment :blush:

You want to change the start value for j because you want j to always be greater than i, so that you’re always buying before you sell. If you change the end value but not the start value, then it is still possible to have j = 1 when i = 2 (for example), but this means selling before you buy, which doesn’t make sense! :smile:

Nice solution! Your basic solution is extremely neat and elegant. Your intermediate solution is lovely and compact. The performance issue is that you’re finding O(2n) possible combinations!

By the way, thanks for the heads up for the market crash :smile: ! I actually included some code to handle that case but it was wrong in a number of places. I gave you a shoutout in my edit :yum:.

Ok, now I understand it, thanks for the explanation :wink:

Improved Basic Solution (O(n))

function bestDays(days){
  var maxDiff = -Infinity;
  var buyDay = 0, sellDay = 0;
  var j = 0; // This var tracks the index of the current min value
  for (var i=1; i<days.length; i++) {
    if (days[i]-days[j]>maxDiff) {
      maxDiff = days[i]-days[j];
      buyDay=j;
      sellDay=i;
    }
    if (days[i]<days[j]) { // I've found a new min value
      j = i;
    }
  }
  return `Buy at day ${buyDay} and sell at day ${sellDay}`;
}
1 Like