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

Posted in

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

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

    Sample Output:

    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[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:

    Leave a Comment on this Post

    0 Comments