In this HackerRank Stock Maximize problem solution, Your algorithms have become so good at predicting the market that you now know what the share price of Wooden Orange Toothpicks Inc. (WOT) will be for the next number of days.
Each day, you can either buy one share of WOT, sell any number of shares of WOT that you own, or not make any transaction at all. What is the maximum profit you can obtain with an optimum trading strategy?
Problem solution in Python.
for case in range(int(input())): N = int(input()) prices = [int(x) for x in input().split()] shares = 0 profit = 0 m = max(prices) while len(prices) > 0: day = prices.pop(0) if day == m: profit += day*shares shares = 0 if len(prices) > 0: m = max(prices) elif day < m: profit -= day shares += 1 print(profit)
Problem solution in Java.
import java.io.*; import java.util.*; public class Solution { static int[] readInt(Scanner in){ int n = in.nextInt(); int[] r = new int[n]; for(int i=0;i<n;i++){ r[i]= in.nextInt(); } return r; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int tc = in.nextInt(); for(int i=0;i<tc;i++){ int a[] = readInt(in); boolean b[] = new boolean[a.length]; int max = a[a.length-1]; b[b.length-1]=true; for(int j=a.length-2;j>-1;j--){ if( (b[j] = (a[j]>max)) ){ max = a[j]; } } long money = 0; long stocks = 0; for(int j=0;j<a.length;j++){ if(b[j]){ money+=a[j]*stocks; stocks=0; }else{ stocks++; money-=a[j]; } } System.out.println(money); } } }
Problem solution in C++.
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <queue> #include <cstring> using namespace std; typedef long long LL; const int N = 1000009; const int Mod = 1000003; int n, a[N], cnt[N]; int main(){ int ca; for(scanf("%d", &ca); ca--; ){ memset(cnt, 0, sizeof(cnt)); scanf("%d", &n); priority_queue<int> que; for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); que.push(a[i]); } LL ans = 0; for(int i = 1; i <= n; i++){ cnt[a[i]] ++; while(cnt[que.top()]){ cnt[que.top()] --; que.pop(); } if(a[i] < que.top()) ans += que.top() - a[i]; } cout << ans << endl; } return 0; }
Problem solution in C.
#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int tc, i,days,*stocks; unsigned long long max=0, p=0, sum=0, c=0; scanf("%d",&tc); while(tc--){ max=p=sum=c=0; scanf("%d",&days); stocks = (int *)malloc(days*sizeof(int)); for(i=0;i<days;i++) scanf("%d",&stocks[i]); for(i=days-1;i>=0;i--) if(max<stocks[i]){ p += (max*c)-sum;//if c=sum=0 max=stocks[i]; c=sum=0; } else {//stocks[i]==max, ok p will be zero sum += stocks[i]; c++; } p += (max*c)-sum;//if stocks[0] is also added up to sum else will be zero only printf("%un",p); free(stocks); } return 0; }