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

By | October 29, 2021
Find maximum profit earned by buying and selling shares any number of times

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

Sample Output:

7

Explanation: 

First buy : 1st index (0-based indexing)

First sell : 2nd index

Second Buy: 3rd index

Second sell: 4th index

Vamware

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[0];  //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[0];  //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[0]);
    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:

Author: Vinay

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published. Required fields are marked *