Google Interview Question
Software EngineersCountry: United States
Looks like you understood the question pretty well. Can you please explain the question ?
Does this take care of the restriction "after you sell your stock, you cannot buy stock on next day" ?
int main() {
int a[] = {30,30,15,18,20,25,80};
int n = sizeof(a)/sizeof(a[0]);
int profit[n];
int mn[n];
mn[n-1] = a[n-1];
int minVal = a[0];
profit[0] = 0;
for(int i=1;i<n;i++) {
profit[i] = max(profit[i-1],a[i]-minVal);
minVal = min(minVal,a[i]);
}
for(int i=n-2;i>=0;i--) {
mn[i] = min(mn[i+1],a[i]);
}
for(int i=4;i<n;i++) {
profit[i] = max(profit[i],profit[i-1]);
for(int j=i-3;j>=1;j--) {
profit[i] = max(profit[i],(max(a[i]-mn[0], profit[j]+(a[i]-mn[j+2]))));
}
}
for(int i=0;i<n;i++)
cout<<profit[i]<<" ";
cout<<profit[n-1]<<endl;
return 0;
}
int main() {
int a[] = {30,30,15,18,20,25,80};
int n = sizeof(a)/sizeof(a[0]);
int profit[n];
int mn[n];
mn[n-1] = a[n-1];
int minVal = a[0];
profit[0] = 0;
for(int i=1;i<n;i++) {
profit[i] = max(profit[i-1],a[i]-minVal);
minVal = min(minVal,a[i]);
}
for(int i=n-2;i>=0;i--) {
mn[i] = min(mn[i+1],a[i]);
}
for(int i=4;i<n;i++) {
profit[i] = max(profit[i],profit[i-1]);
for(int j=i-3;j>=1;j--) {
profit[i] = max(profit[i],(max(a[i]-mn[0], profit[j]+(a[i]-mn[j+2]))));
}
}
for(int i=0;i<n;i++)
cout<<profit[i]<<" ";
cout<<profit[n-1]<<endl;
return 0;
}
We might want to use DP for this problem because of its subproblem nature for maximum profit.
#include <iostream>
#include <stdlib.h>
using namespace std;
int maxProfitRec(int a[],int i,int n) {
if(i >= n) return 0;
int mx1 = maxProfitRec(a,i+1,n);
return max(mx1, a[i]+maxProfitRec(a,i+2,n));
}
int maxProfit(int a[],int n) {
int table[n+1];
table[0] = table[1] = 0;
for(int i=2;i<=n;i++) {
int mx = table[i-1];
for(int j=i-2;j>=0;j--) {
mx = max(table[j]+a[i-1],mx);
}
table[i] = mx;
}
return table[n];
}
int main() {
int a[] = {3,5,2,5,60,12,5,234,5,223,123};
int n = sizeof(a)/sizeof(a[0]);
cout<< "DP Algo :"<<maxProfit(a,n) <<endl;
cout<< "Rec Algo:"<<maxProfitRec(a,0,n) <<endl;
return 0;
}
- lepeisi November 22, 2015