Leetcode: Best Time to Buy and Sell Stock II

 

This question is asked at Amazon, Microsoft, Adobe, Uber, Facebook, Bloomberg, Google, Apple, Walmart, Oracle, and many other companies. Here is the problem: 

You are given an integer array prices where prices[i] is the price of a give stock on the ith day. On each day you decide to buy or sell a stock but you can only hold at most one share of the stock, but can buy and sell the stock on the same day. I want to find and return the maximum profit I can achieve. Here's an example:

The prices are [7, 1, 5, 3, 6, 4] and the output is 7 which indicates the total profit I can have. If I buy on day 2 and sell on day 3 I make a profit of $4. Now If I buy on day 4 and sell on day 5 I make a profit of $3. The total profit is $4 + $3 = $7. 

There are several ways that we can approach this. The first approach that we can try to veer towards is the brute force approach. This is us calculating the profit for all sorts of transactions and extracting the maximum profit out of them. For each of the 2 prices we try to find whenever the later price is greater than the earlier price. We calculate the profit, and keep track of a maximal variable, in order to finally compute the value for maximum profit. 

Here's the brute force solution. 

class Solution {

    public int maxProfit(int[] prices) {

        return calculate(prices, 0); //calculate from beginning to end 

}

    public int calculate(int[] prices, int s) {

        if(s >= prices.length) return 0; //invalid entry 

        int max = 0;

        for(int start = s; start < prices.length; start++) {

            int maxprofit = 0;

            for(int i = start + 1; i < prices.length; i++) {

                int profit = prices[i] - prices[start] + calculate(prices, i + 1); //add optimal prices from the future recursively. 

                if(profit > maxprofit) maxprofit = profit; //update if profit is greater

            }

            if(maxprofit > max) max = maxProfit; //update if profit is greater. 

        }

        return max; 

    }

}

The second method we can try to apply to solve this problem is a peak valley approach. for total profit, we need to look at the peak, then the valley, then calculate the sums of all of these peaks. We consider every peaks following a valley. This will follow a single pass and take O(n) time complexity. 

class Solution {

    public int maxProfit(int[] prices) {

        int i = 0;

        int valley = prices[0]; 

        int peak = prices[0]; //global minima and maxima, respectively. 

        int maxprofit = 0;

        while (i < prices.length - 1) {

            while(i < prices.length - 1 && prices[i] >= prices[i + 1]) i++; //find the first valley.

            valley = prices[i];

            while(i < prices.length - 1 && prices[i] <= prices[i + 1]) i++;  //find the first peak.

            peak = prices[i]; 

            maxprofit += peak - valley;  //take the difference and add this to the profit amount. 

        }

        return maxprofit; 

    }

}