# Find maximum profit earned by buying and selling shares any number of times

Posted in  Vinay Khatri
Last updated on July 16, 2022

## Problem

You are provided an array of prices, where prices[i] represents the current price of a specific stock. Determine your greatest profit potential. You are free to complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). It is important to note that you may not do several transactions at the same time (i.e., you must sell the stock before you buy again).

#### Sample Input:

`7,1,5,3,6,4`

`7`

#### Explanation:

First buy : 1st index (0-based indexing) First sell : 2nd index Second Buy: 3rd index Second sell: 4th index

## Brute Force Approach

In this example, we simply compute the profit associated with all conceivable sets of transactions and determine the greatest profit from them. This approach may become inefficient for a large number of stocks.

## Efficient approach

We can keep track of local minimas in this problem. This smallest element will denote our buying price.  Whenever we find an element that is greater than its next element, we can sell the stock at this position. You can prove that this will always give the optimal solution because we are utilizing the maximum difference that we can obtain. For instance, given an array: ``` 7,1,5,3,6,4 ``` We are at index 0. As soon as 1 comes after the current index, we add 0 to answer as 7 was the smallest element upto 0. When 3 comes after 5, we add 4(5-1) to the sum and so on.

### C++ Programming

```#include<bits/stdc++.h>
using namespace std;
int maxProfit(vector<int>& prices) {
int n=prices.size();
int smallest=prices;  //keep track of minimum price
prices.push_back(-1);
int ans=0;
for(int i=0;i<n;i++){
if(prices[i]>prices[i+1]){  //if we find an element that is greater than its next one
if(prices[i]>smallest){
ans+=prices[i]-smallest;  //update the answer because its best time to sell
smallest=prices[i+1];
continue;
}
}
smallest=min(smallest, prices[i]);
}
return ans;
}
int main(){
vector<int>v{1, 4, 1, 2, 5};
cout<<maxProfit(v);
}```

Output

`7`

### C Programming

```#include<stdio.h>
int min(int a, int b){
return a>=b?b:a;
}
int maxProfit(int* prices, int n){
int smallest=prices;  //keep track of minimum price
int ans=0;
for(int i=0;i<n-1;i++){
if(prices[i]>prices[i+1]){  //if we find an element that is greater than its next one
if(prices[i]>smallest){
ans+=prices[i]-smallest;  //update the answer because its best time to sell
smallest=prices[i+1];
continue;
}
}
smallest=min(smallest, prices[i]);
}
if(prices[n-1]>smallest) ans+=prices[n-1]-smallest;
return ans;
}
void main(){
int prices[] = {1, 4, 1, 2, 6};
int n = sizeof(prices)/sizeof(prices);
printf("%d", maxProfit(prices, n));
}```

Output

`8`

### Fairly simple Solution in Python

Just update the profit whenever the current element is greater than its previous one. This approach ultimately gives the same optimal answer.

```def maxProfit(prices):
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]

return profit
l = [1, 2, 1, 4, 2]
print(maxProfit(l))```

Output 4 People are also reading: