Scribble 14: Maximize Profit Part 2

Here’s the problem statement:

GIven an array of integers that represent the worth of stock on consecutive days, find the maximum profit  that can be made by buying stock on any day and then selling it on another day in the future. You are allowed multiple buy-sell transactions. However, you cannot both buy and sell stock on the same day. 

For example:
The Array: [7, 1, 5, 3, 6, 9]
Output: 10 (buy at price = 1 and sell at price = 5, buy at price = 3 and sell at price = 9)

Let’s dive into the solution:

Note that to maximize profit, we must add up all profit wherever it is possible. Therefore whenever there is an uphill in the array among the consecutive values, we must buy at the start of the bottom most value in the ascent and sell at the peak. And we must simply skip over the downhill descents on consecutive days because buying at their start and selling during them/at their end bears no profit.

For instance, in the given example, ‘1’ is the start of an ascent whose peak is ‘5‘, so we must add up 4(=5-1) in profit. Again, ‘3’ is the start of an ascent whose peak is ‘9‘, so we must add up 6(=9-3) in profit.

It is good to note that the code structure of this problem is similar to Approach 1 of Longest Mountain Range in the Array Problem.

Time complexity: O(N) since we go over every element only once

Space complexity: O(1) because we do not use any extra storage space.

Here’s the code for this solution in Java:

public int maximizeProfit(int[] array) {
        int cp, profit, i;
        profit = i = 0;
        while(i<array.length) {
            if((i+1)<array.length && array[i]<array[i+1]){ //start of an ascent 
                cp = array[i];
                while((i+1)<array.length && array[i]<array[i+1])//when this loop ends then i points to the peak
                    i++;
                profit += array[i]-cp;
            }
            else
                i++;
        }
        return profit;
}

Hey there! 🙂 Today’s the last day of the Code Spree! We extensively covered array based coding problems in this chapter. Hope you had fun! It’ll be great if you’d provide some feedback. To reach out, please leave a comment in the Contact section. Thanks! Until next time, Happy Coding! 🙂