Best time to buy and sell stock II

Peak Valley Approach

The brute force approach exceeds the time limit, so let's optimize it using the peak valley approach. In this approach, we consider every peak value that is immediately followed by a valley. Let us discuss the algorithm used in this approach. 

Algorithm

• Initialize maxProfit = 0. Initially, consider the first stock value as both the peak and valley for a new transaction.
• Linearly iterate over the arr[] array starting from day two or index = 1 to the end of the array.  
• Check if the current stock price is greater than the previous stock price. If it is true, the current stock price will peak.
• If the last price is the peak stock price, then maxProfit = maxProfit + (peak - valley).
• If the current stock price is not greater than the previous, then maxProfit = maxProfit + (peak - valley). The new transaction should start from the ith day.
• The valley will be arr[i], and the new peak will be the valley.
• Return the maxProfit.

Dry Run

Let us try to analyze the input and output carefully according to the algorithm

arr = {2, 4, 7, 1, 3, 5}

Let’s plot the stock arr on a graph, and try to visualize a pattern.

It can be easily observed that buying the stock on crests and selling on the first peaks will give the maximum profit.

So, Total profit = profit in transaction 1 + profit in transaction 2 = 5 + 4 = 9.

Implementation

The implementation of the algorithm is given below:

public class Main {
	public static int maxProfit(int[] arr) {
    	int maxprofit = 0;
    	
    	// To store the valley i.e the lowest price for a new transaction.
    	int valley = arr[0];
    	
    	// To store the peak i.e the maximum price for a new transaction.
    	int peak = arr[0];
    	
    	for (int i = 1; i < arr.length; i++) {
    	    /* If the current price is not less than previous price, 
    	       it will be the new peak
        	       for current transaction.*/
        	    if (arr[i] >= arr[i - 1]) {
                   peak = arr[i];
            	
                   // If the last price is a peak value.
                   if (i == arr.length - 1)
                   maxprofit += peak - valley;
            } 
            else {
                /* We found a new valley, so we 
                    will end our current transaction completes.*/
                maxprofit += peak - valley;
            	
                // New transaction should start from ith day.
                valley = arr[i];
                peak = valley;
            }
        }
    	return maxprofit;
    }
    public static void main(String[] args) {
        int[] arr1 = {1, 3, 8, 2, 4};
        int[] arr2 = {25, 32, 81, 2, 95};
        int[] arr3 = {3, 95, 25, 36, 74, 98};
        System.out.println("The maximum profit possible from arr1[] is " +maxProfit(arr1));
        System.out.println("The maximum profit possible from arr2[] is " +maxProfit(arr2));
        System.out.println("The maximum profit possible from arr3[] is " +maxProfit(arr3));

    }
}

You can also try this code with Online Java Compiler

Run Code

Output

The output of the above program is:

Complexity Analysis

Time Complexity

The time complexity of the above program is O(N), as in the worst case, we will be iterating over the input array once.

Space Complexity

The space complexity is O(1) as no extra space is required.

Positive Slopes Approach

So far, so good. We have successfully optimized the brute force approach from O(N^N) time complexity to O(N) time complexity. The concept of peaks and valleys discussed above can be further modified to obtain the solution much more efficiently.

Algorithm

1. Initialize maxProfit equal to 0.
2. Linearly iterate over the array. If the current price is greater than the previous price, or a positive slope is formed between the previous price and the current price. Then the current price - the previous price will be added to the maximum profit.
3. Return the maximum profit.

Dry Run

Let's carefully see the graph for stock arr[] = {2, 4, 7, 1, 3, 5}

From the graph, you can easily calculate the profit as 9 in this case.

If you observe carefully, you will notice that the profit is equal to the difference of all the consecutive price pairs wherein each pair's price on an ith day is greater than the price on (i-1)th day.

In the above example, the possible pairs will be:

You must try other examples in the same way we discussed above on your own to understand the intuition behind them. 

Implementation

The implementation of the algorithm is given below:

public class Main {
public static int maxProfit(int[] arr) {
     // Initialize maxprofit equal to 0
     int maxprofit = 0;
    
     // Linearly iterate over the array
     for (int i = 1; i < arr.length; i++) {
         /* If the current price is greater than 
           previous price, it should be added to 
           the maxprofit.*/
         if (arr[i] >= arr[i - 1]) {
                maxprofit += arr[i] - arr[i - 1];
            }
        }
     return maxprofit;
    }
    public static void main(String[] args) {
        int[] arr1 = {1, 3, 8, 2, 4};
        int[] arr2 = {25, 32, 81, 2, 95};
        int[] arr3 = {3, 95, 25, 36, 74, 98};
        System.out.println("The maximum profit possible from arr1[] is " +maxProfit(arr1));
        System.out.println("The maximum profit possible from arr2[] is " +maxProfit(arr2));
        System.out.println("The maximum profit possible from arr3[] is " +maxProfit(arr3));
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

The output of the above program is:

Complexity Analysis

Time Complexity

The time complexity using the above approach is O(N). This is because we have done only one iteration starting from 1 to N, where N = length of the given array. 

Space Complexity

The space complexity is O(1), as no extra space is required. 

Frequently Asked Questions

What is recursion?

Recursion is the better way of solving a problem. It divides the problem into smaller parts calling the recursive function repeatedly.

What the problem “Best time to buy and sell stock ii” states?

The best time to buy and sell stocks II problem states that you have to find the maximum profile earned when you are allowed to buy and sell as many stocks as you want. 

What is the peak valley approach?

In the peak valley approach, we consider every peak value that is immediately followed by a valley. 

How is memoization helpful in solving problems?

Memoization helps in recording the data, which is calculated onces so that we don't need to calculate it again and again. It helps in saving a lot of time and cost. 

What is the time complexity to solve the problem?

The time complexity to solve this problem using brute force is O(N*N) and optimize approach is O(N).

Conclusion

The blog discussed an important interview problem, the best time to buy and sell stock ii. Various approaches, along with code, were discussed. With this done, you may practice more questions related to Arrays.
You can refer to other such problems using below links:

• Beautiful Arrangements
• Aggressive cows
• Book allocation
• Boats to save people
   

Please refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, Java Programming, and System Design, etc. Have a look at the interview experiences and interview bundle for placement preparations. And also, enroll in our courses and refer to the mock test and problems available.

If you think that this blog helped you, then share it with your friends!

All the best for your future endeavors, and Keep Coding.