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. What 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
Code Implementation
//
// 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.