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

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

• Count the number of strictly increasing subarrays in an array
• Find duplicates within a range k in an array
• Longest Subarray with Contiguous Elements
• Find the smallest subarray length whose sum of elements is >= k
• Determine the index of an element that satisfies given constraints in an array
• Find the smallest window in an array sorting which will make the entire array sorted
• Print all triplets that form a geometric progression
• Shuffle an array according to the given order of elements
• Find equilibrium index of the array
• Reverse every consecutive m-elements of a subarray