Amazon | Phone | Buy Sell Stock - Multiple transactions allowed.
Arjun Dass
9607
AmazonPhone ScreeningInterview

You are given amzon's stock price for everyday. You are allowed to buy stocks (multiple transactions allowed) every day without any transaction fees. Calculate Maximum profit.

While Interviewing I told him the brute force solution which was accepted, then he asked me to optimize it. I was at first thinking that multiple transactions are not allowed but he cleared my doubts. So we came up with a solution, that we should first look for the latest upcoming maxprice, if the there is one, then buy stocks till that date and then sell it on that particular day and then do the same for the rest of the subarray. And if the current day (index) is maximum then just go to the next index and perform the same calculations.

The fact that it allows mulitple transaction made it a little tricky. I was able to tell him the solution and told him that we will be approaching it using recurrsion and he was impressed by it but I ran out of time. Was almost on verge of completing my recurrsion function. Here's my solution.

// "static void main" must be defined in a public class.

/*
{ 10, 12, 15, 12, 31, 24, 23, 10, 4, 14 }


*/
class Main {
    public static void main(String[] args) {
        Main obj = new Main();
        int[] x = { 10, 11, 13, 14, 16, 18, 17, 10, 4, 14 };
        System.out.println(obj.maxProfit(x));
    }
    
    public int maxProfit(int[] prices) {
        int profit = 0;
        int maxProfit = helper(0, prices.length-1, prices, profit);
        return maxProfit;
    }
    
    private int helper(int startIndex, int endIndex, int[] prices, int profit) {
        int maxElement = prices[startIndex]; 
        int maxElementIndex = startIndex;
        
        for (int i=startIndex; i<endIndex; i++) {
           if (prices[i] > maxElement) {
               maxElement = prices[i];
               maxElementIndex = i;
           }
        }
        
        if (maxElementIndex == startIndex) {
            return helper(startIndex+1, prices.length, prices, profit);    
        }
        
        if (maxElementIndex == prices.length - 1) {
            for (int i=startIndex; i<=maxElementIndex; i++) {
                profit += (maxElement - prices[i]);
            }
            return profit;
        } else {
            
            for (int i=startIndex; i<=maxElementIndex; i++) {
                profit = profit + (maxElement - prices[i]);
            }
            return helper(maxElementIndex + 1, prices.length, prices, profit);
        }
         
    }
}

I was in the else part of my recursion function when the time ran out. Haven't heared from the recruiter yet, but not keeping high hopes.

Thank you

UPDATE: I was specifically told that you can only start from the first day, i.e first index

Comments (29)