maximum profit on selling shares

Question

Your algorithms have become so good at predicting the market that you now know what the share price of Wooden Orange Toothpicks Inc. (WOT) will be for the next number of days.

Each day, you can either buy one share of WOT, sell any number of shares of WOT that you own, or not make any transaction at all. What is the maximum profit you can obtain with an optimum trading strategy?

For example, if you know that prices for the next two days are prices=[1,2], you should buy one share day one, and sell it day two for a profit of 1. If they are instead [2,1], no profit can be made so you don't buy or sell stock those days.

Sample Input

3

5 3 2

3

1 2 100

4

1 3 1 2

Sample Output

0

197

3

My code is:

static int stockmax(int[] prices) {
  int temp[][]=new int[prices.length][prices.length];
    int max;
    int sum=0;
    for(int i=0;i<prices.length;i++)
    {
        max=0;
        for(int j=0;j<prices.length;j++)
        {
            if(j<=i)
            {
                temp[i][j]=0;
            }
            else{
                temp[i][j]=prices[j]-prices[i];
            }
            if(temp[i][j]>max)
                max=temp[i][j];
        }
        sum+=max;
    }
    return sum;
}

I am getting the wrong answer to this question. Can anyone say why is this code wrong?

Yes, my logic does account selling multiple shares on a day. Suppose it is 5 4 3 4 5 then my code accounts for selling 4,3,4 on 5. — Karan Matalia
@JoakimDanielson The first line of the input is the number of test cases, followed by a line with number of days in the test case and another line with the prices. — jpw
I think the code is fine (although I would start second loop at i + 1 and remove temp[][] and use just an int variable). How do you know the code is wrong? The wrong part might be somewhere else — juvian

גלעד ברקן גלעד ברקן · Accepted Answer · 2018-09-03T20:17:06

Clearly, for any price we can buy, we would want to sell it at the highest price. Fortunately, we are given that highest price. So, iterating backwards, we know the highest future price seen at any point we visit in our travel "back in time."

Python code:

def stockmax(prices):
  n = len(prices)
  highest = prices[n - 1]
  m = [0] * n

  # Travel back in time,
  # deciding whether to buy or not
  for i in xrange(n - 2, -1, -1):

    # The most profit buying stock at this point
    # is what we may have made the next day
    # (which is stored in m[i + 1])
    # and what we could make if we bought today
    m[i] = m[i + 1] + max(
      # buy
      highest - prices[i],
      # don't buy
      0
    )

    # Update the highest "future price"
    highest = max(highest, prices[i])

  return m[0]

maximum profit on selling shares

1 Answers