We all study hard for placements, solve numerous questions related to DSA, study Computer Science Fundamentals, and learn how to design a scalable system. The ultimate goal is to crack our dream job. One important question commonly asked in interviews is, "Best time to buy and sell stock".

This blog will discuss the Best time to buy and sell stock ll, wherein the proces of the stocks will be stored in an array. You need to find the maximum profit possible.

Problem Statement

There are mainly three variations to this problem, the first one is where you can buy and sell a single stock, the second one is when you can buy and sell as many stocks as you want, and the third one is where you can buy at most K Stocks. Here we are going to solve the problem where we can buy and sell as many stocks as we want, i.e., the second type. It is recommended to solve this problem on your own before moving on.

In an interview, it is recommended first to analyze the problem statement properly. The problem statement on hand says there is an integer array arr[] where arr[i] is a given stock's price on an ith day. You need to find out the maximum profit possible with the following conditions:

On each day, you may either buy or sell a stock.

At most, one stock can be held at any time.

Purchasing and selling stock on the same day is possible.

Let us look at some examples before discussing the approach of solving the problem:

Example 1:

Input: {2, 4, 7, 1, 3, 5}

Output: 9

Explanation:

Buy on day 1(arr[] = 2) and sell on day 3(arr[] = 7), profit =7-2 = 5

Buy on day 4(arr[] = 1) and sell on day 6(arr[] = 5), profit = 5-1 = 4

Total profit is 5 + 4 = 9.

Example 2:

Input: {7, 6, 5, 2, 4}

Output: 2

Explanation:

Buy on day 4(arr[] = 2) and sell on day 5(arr[] = 4), profit =4-2 = 2

There is no other combination possible because all other values are in descending order.

Example 3:

Input: {5, 8, 1, 6, 3}

Output: 8

Explanation:

Buy on day 1(arr[] = 5) and sell on day 2(arr[] = 8), profit =8-5 = 3

Buy on day 3(arr[] = 1) and sell on day 4(arr[] = 6), profit =6-1 = 5

Total profit is 3 + 5 = 8.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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));
}
}

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

Initialize maxProfit equal to 0.

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.

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));
}
}

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: