CareerCup

example would be, given stock prices like this:
9 2 5 6 6 1 3 7

we should buy at price 1 then sell at 7. we cannot buy at 1 then sell at 9 since it is in the past.

O(n) time and space with dynamic programming:

def profit(arr):
    table = [0 for x in arr]
    maxs = [0 for x in arr]
    maxs[-1] = arr[-1]
    for i in range(len(arr)-2, -1, -1):
        maxs[i] = max([maxs[i+1], arr[i]])
    bought, sold = arr[-1], arr[-1]
    for i in range(len(arr)-2, -1, -1):
        this = maxs[i] - arr[i]
        if this > table[i+1]:
            table[i] = this
            bought = arr[i]
            sold = maxs[i]
        else:
            table[i] = table[i+1]
    return (table[0], bought, sold)

O(n) algorithm in one pass.


def maxprofit(prices):
buydate, selldate = 0, 0

maxprof = 0
minprice = prices[0]
mindate = 0

for d, p in enumerate(prices[1:]):
if p < minprice:
minprice = p
mindate = d + 1
continue

prof = p - minprice

if prof > maxprof:
maxprof = prof
buydate, selldate = mindate, d + 1

return (buydate, selldate), maxprof

Can you place elaborate the question a little bit. May be add some example?

Yeah calculate difference in stocks for each successive days and compute maximum contiguous sum which can be done in o(nlogn) using divide and conquer

possible solution. to get max profit is straightforward.

public void findBestPrices(int[] prices){
        int lowIndex = 0;
        int highIndex = 0;
        
        if(prices.length==0||prices.lenght==1){
            //error message
        }else{
            for(int i=1;i<prices.length;i++){
                if(prices[i]<prices[lowIndex]){
                    if(i!=prices.length-1){ //if last element is lowest, don't change
                        lowIndex = i;
                        highIndex = i;
                    }
                }
                if(prices[i] > prices[highIndex]){
                    highIndex = i;
                }
            }
        }
        System.out.println("Lowest Price " + prices[lowIndex] +
                " Highest Price " + prices[highIndex]);
    }

O(n) complexity algorithm:

prev = arr[0];
current = arr[0];
profit = 0;
for(i =0 to n-2)
{
   if(arr[i+1]<arr[i])
   {
       sum += (arr[i]-prev);
       prev = arr[i+1];
   }
}

sry.. made an extra variable in above solution

prev = arr[0];
profit = 0;
for(i =0 to n-2)
{
   if(arr[i+1]<arr[i])
   {
       profit += (arr[i]-prev);
       prev = arr[i+1];
   }
}

Buy when it low and sell when it high. which mean you buy a[i] when a[i+1] > a[i] and sell when a[i+1] < a[i]. In the example above add 0 after 7 to have 9 2 5 6 6 1 3 7 0, in this example you will buy 2 since 3>2 and sell at 6 since 1<6, buy again at 1 and sell at 7. Total profit 4+6 = 10.

I guess what interviewer meant here was that there is a series of profits and loss of a particular stock. so the array might have -ve elements also. hence we have to find the index where he has to buy the stock and the index where he has to sell the stock.

Thus basically we have to find the Maximum Subarray in an array.

Hope I made my point!!

#include<iostream>
using namespace std;

struct node
{
int low;
int high;
int sum;
} *left,*right,*cross;

node *dncCross(int arr[],int l,int m,int h)
{
int leftsum=-100;
int sum=0;
node *tmp;
tmp=new node;
for(int i=m;i>=0;i--)
{
sum=sum+arr[i];
if(leftsum<sum)
{

leftsum=sum;
tmp->low=i;
}

}
int rightsum=-100;
sum=0;
for(int i=m+1;i<h;i++)
{
sum=sum+arr[i];
if(rightsum<sum)
{
rightsum=sum;
tmp->high=i;
}
}
tmp->sum=leftsum+rightsum;
return tmp;
}

node *dnc(int arr[],int l,int h)
{
node *temp,*tl,*tr,*tc;
temp=new node;
tl=new node;
tr=new node;
tc=new node;
if(l==h)
{
temp->low=l;
temp->high=l;
temp->sum=arr[l];
return temp;

}

int mid;
mid=(l+h)/2;
tl=dnc(arr,l,mid);
tr=dnc(arr,mid+1,h);
tc=dncCross(arr,l,mid,h);
//cout<<"***"<<tl->sum<<endl;
if(tl->sum>tr->sum&& tl->sum>tc->sum) return tl;
if(tr->sum>tl->sum&& tr->sum>tc->sum) return tr;
if(tc->sum>tr->sum&& tc->sum>tl->sum) return tc;
}

int main()
{
int n;
// left->low=-1;
//left->high=-1;
//left->sum=-100;
cout<<"\nEnter the strength of the array:";
cin>>n;
int arr[n];
cout<<"\nEnter the values of the elements in the array";
for(int i=0;i<n;i++)
{
cin>>arr[i];
}

node *result;
result=new node;
result=dnc(arr,0,n);
cout<<"he should buy at "<<result->low<<" and sell the stock at "<<result->high;
cout<<"The Sum of max Profit"<<result->sum;
cin>>n;
return 0;
}

Can be solved by finding the Maximum difference between two elements of an array, provided the greater number is on the right side.

package javaapplication1;

import java.io.IOException;

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

/**
*
* @author kras
*/
public class Excersice2 {

static int counter = 0;

public void findBiggestProfit(int[] array) throws IOException
{
Data profit = findBiggestProfit(array, 0, array.length - 1);

System.out.println(profit.getProfit());
}

private Data findBiggestProfit(int[] values, int start, int end) throws IOException
{
if (start == end)
{
counter++;
return new Data (values[start], values[end]);
}
else
{
int mid = start + (end - start) / 2;

Data leftData = findBiggestProfit(values, start, mid);
Data rightData = findBiggestProfit(values, mid + 1, end);

Data newProfit = new Data(leftData.getMin(), rightData.getMax());

return getBiggestProfit(leftData, rightData, newProfit);
}
}

private Data getBiggestProfit(Data d1, Data d2, Data d3)
{
if (d1.getProfit() > d2.getProfit() && d1.getProfit() > d3.getProfit())
{
return d1;
}
if (d2.getProfit() > d1.getProfit() && d2.getProfit() > d3.getProfit())
{
return d2;
}
else
{
return d3;
}
}

private class Data
{
private int value1, value2, profit;

public Data(int value1, int value2)
{
this.value1 = value1;
this.value2 = value2;
this.profit = value2 - value1;
}

public int getMin()
{
return Math.min(value1, value2);
}

public int getMax()
{
return Math.max(value1, value2);
}

public int getProfit()
{
return this.profit;
}
}
}

pseudo code:

bought=false;
for( i=o;i<n;i++)
diff[i]=a[i+1]-a[i];

for(j=0;j<n-1;j++)
{
if(diff[j]>=0)
{
if(bought==false)
{
print " buy on " + j + " day at " + a[j];
bought=true;
}
profit+=diff[j];
}
else
{
if(bought==true)
{
print " sell on " + j + " day at " + a[j];
bought=false;
}
}
}
if(bought==true)
print " sell on " + j + " day at " + a[j];

print "Profit gained: " + profit

Someone might have already posted the same... kindly correct is some issue are with this program.

private static void findMaxGain(int[] a) {
if (a == null && a.length < 2) {
System.out.println("Valid data not provided.");
}

int lowValueIdx = 0, highValueIdx = 0;
int purIdx = 0, sellIdx = 0;
int maxGain = 0;
for (int i = 1; i < a.length; i++) {
if (a[i] < a[lowValueIdx]) {
lowValueIdx = i;
highValueIdx = i;
} else if (a[i] > a[highValueIdx]) {
highValueIdx = i;
if ((a[highValueIdx] - a[lowValueIdx]) > maxGain) {
purIdx = lowValueIdx;
sellIdx = highValueIdx;
maxGain = a[highValueIdx] - a[lowValueIdx];
}
}
}

System.out.println("Maxgain: " + maxGain + " PurchaseIdx: " + purIdx
+ " SellIdx: " + sellIdx);
}

MaxProfit[j] is maximum profit when u sell at position j.

MaxProfit[j]={ 0 if A[j]< A[j-1];
MaxProfit[j-1]+A[j]-A[j-1] if A[j]>=A[j-1]
}

Traverse maxProfit array to find the max value for selling and traverse back from that location to find the first 0 for buyin index

time complexity O(n).
Space complexity O(n)