# Best Time To Buy And Sell Stock

Back to home
Logicmojo - Updated Aug 28, 2021

## Problem Statement: Best Time To Buy And Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example :

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

We have presented two approaches to find the two elements:

• Naive Approach
• Efficient Approach

### Naive Approach

A basic strategy is to try purchasing and selling stocks every day when they are profitable, and to keep track of the total profit thus far.

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

int maxProfit(int price[], int start, int end)
{

if (end <= start)
return 0;

int profit = 0;

for (int i = start; i < end; i++) {

for (int j = i + 1; j <= end; j++) {

if (price[j] > price[i]) {

int curr_profit = price[j] - price[i]
+ maxProfit(price, start, i - 1)
+ maxProfit(price, j + 1, end);

profit = max(profit, curr_profit);
}
}
}
return profit;
}

int main()
{
int price[] = { 100, 180, 260, 310,
40, 535, 695 };
int n = sizeof(price) / sizeof(price[0]);

cout << maxProfit(price, 0, n - 1);

return 0;
}
```

Java Implementation:

```import java.util.*;

class Main
{

static int maxProfit(int price[], int start, int end)
{

if (end <= start)
return 0;
int profit = 0;

for (int i = start; i < end; i++)
{

for (int j = i + 1; j <= end; j++)
{

if (price[j] > price[i])
{

int curr_profit = price[j] - price[i]
+ maxProfit(price, start, i - 1)
+ maxProfit(price, j + 1, end);

profit = Math.max(profit, curr_profit);
}
}
}
return profit;
}

public static void main(String[] args)
{
int price[] = { 100, 180, 260, 310,
40, 535, 695 };
int n = price.length;

System.out.print(maxProfit(price, 0, n - 1));
}
}
```

Python Implementation:

```def maxProfit(price, start, end):

if (end <= start):
return 0;

profit = 0;

for i in range(start, end, 1):

for j in range(i+1, end+1):

if (price[j] > price[i]):

curr_profit = price[j] - price[i] +\
maxProfit(price, start, i - 1)+ \
maxProfit(price, j + 1, end);

profit = max(profit, curr_profit);

return profit;

if __name__ == '__main__':
price = [100, 180, 260, 310, 40, 535, 695];
n = len(price);

print(maxProfit(price, 0, n - 1));
```

### Approach 2: Efficient Approach

f we can only buy and sell once, we can apply the following algorithm. The most significant difference between two parts. We are permitted to buy and sell many times here.

The solution to this problem is as follows.

1. Find the local minima and save it as the index to start with. Return if it doesn't exist.

2. Find and save the local maxima as an ending index. Set the finishing index to the end if we get to the end.

3. Refresh the solution (Increment count of buy-sell pairs)

4. if you haven't reached the end yet, repeat the instructions above.

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

{
if (n == 1)
return;

int i = 0;
while (i < n - 1) {

while ((i < n - 1) && (price[i + 1] <= price[i]))
i++;

if (i == n - 1)
break;

while ((i < n) && (price[i] >= price[i - 1]))
i++;

int sell = i - 1;

<< "\t Sell on day: " << sell << endl;
}
}

int main()
{
int price[] = { 100, 180, 260, 310, 40, 535, 695 };
int n = sizeof(price) / sizeof(price[0]);

return 0;
}
```

Java Implementation:

```import java.util.ArrayList;

class Interval {
}

{
if (n == 1)
return;

int count = 0;

ArrayList<Interval> sol = new ArrayList<Interval>();

int i = 0;
while (i < n - 1) {
while ((i < n - 1) && (price[i + 1] <= price[i]))
i++;

if (i == n - 1)
break;

Interval e = new Interval();

while ((i < n) && (price[i] >= price[i - 1]))
i++;

e.sell = i - 1;

count++;
}

if (count == 0)
System.out.println("There is no day when buying the stock "
+ "will make profit");
else
for (int j = 0; j < count; j++)
+ "	 "
+ "Sell on day : " + sol.get(j).sell);

return;
}

public static void main(String args[])
{

int price[] = { 100, 180, 260, 310, 40, 535, 695 };
int n = price.length;

}
}
```

Python Implementation:

```def stockBuySell(price, n):

if (n == 1):
return

i = 0
while (i < (n - 1)):

while ((i < (n - 1)) and
(price[i + 1] <= price[i])):
i += 1

if (i == n - 1):
break

i += 1

while ((i < n) and (price[i] >= price[i - 1])):
i += 1

sell = i - 1