Stock Buy Sell Maximum Profit Solution

Problem

The cost of a stock on each day is given in an array. Each day, you can either buy one share, sell any number of shares that you own, or not make any transaction at all. Find is the maximum profit that you can make?

Input

The first line contains the number of test cases T.
Each of the next T pairs of lines contain:
– The first line contains an integer n, the number of predicted prices of share.
– The next line contains n space-separated integers prices[i], each a predicted stock price for day.

Output

Output T lines, each containing the maximum profit which can be obtained for the corresponding test case.

Constraints

  • 1 ≤ T ≤ 10
  • 1 ≤ n ≤ 50000
  • 1 ≤ prices[i] ≤ 100000

Sample Input

3
3
5 3 2
3
1 2 100
4
1 3 1 2

Sample Output

0
197
3

Solution

//
//  main.cpp
//  Stock Buy Sell Maximum Profit
//
//  Created by Himanshu on 16/02/22.
//
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

int main() {
    int T, n, buyCtr;
    long long ans, maxSellPrice;
    
    cin>>T;
    
    while (T--) {
        ans = 0;
        maxSellPrice= 0;
        buyCtr = 0;
        
        cin>>n;
        
        long long *prices = new long long[n]();
        long long *maxSellPriceArr = new long long[n]();
        
        for (int i=0; i<n; i++) {
            cin>>prices[i];
        }
        
        for (int i=n-1; i>=0; i--) {
            if(prices[i] > maxSellPrice) {
                maxSellPriceArr[i] = prices[i];
                maxSellPrice = prices[i];
            } else {
                maxSellPriceArr[i] = maxSellPrice;
            }
        }
        
        for (int i=0; i<n; i++) {
            if(prices[i] < maxSellPriceArr[i]) {
                buyCtr++;
                ans -= prices[i];
            } else {
                ans += buyCtr*maxSellPriceArr[i];
                buyCtr = 0;
            }
        }
        
        cout<<ans<<endl;
    }

    return 0;
}

Time Complexity: O(n), n is the size of input array – prices.

Leave a Reply

Your email address will not be published.