CareerCup

traverse the price sequence ,maintain the minimum price so far,and update the max profit with a[i]-min
time complexity O(n)

int maxProfit(vector<int> &a) 
 {
        if(a.size()==0)return 0;
        int min=a[0];
        int best=0;
        for(int i=1;i<a.size();i++)
        {
            int tmp = a[i]-min;
            best = max(best,tmp);
            if(a[i]<min)min=a[i];
        }
        return best;
    }

My solution at the end was:

Store difference from each consecutive day in an array of size n-1 (as size of original array is 1). So now we just have to find a continuous sequence of numbers(in the difference array) whose sum is maximum and that would give us max benefit

For instance lets say
original price array = [150 ,149 ,155, 157, 137, 150, 167]
difference price array = [ -1, 6, 2, -20, 13, 17]

So in difference array 1element represent the profit or loss(if -ve) if one buys stock on first day and sells on 2nd day

Now the problem reduces to maximum sum in subarray which can be easily calculated by Kandane's Algo in worst case O(n)

First approach: O(n^2)
Global variables : maxProfit, maxSellValue, maxBuyValue
- start from the end , and for each index j(consider it selling value) find the max profit by computing a[j] - a[i] where i < j. Put in maxProfit the max profit found if bigger than maxProfit and store in maxSellValue the value from index j and in maxBuyValue the value from index i.
- return maxSellValue and maxBuyValue.

Example:
array = [150 ,149 ,155, 157, 137, 150, 167]

j = 6 : maxProfit = 30 maxSellValue = 167 maxBuyValue = 137
j = 5: the three values are the same
j = 4: the three values are the same
j = 3: the three values are the same
j = 2: the three values are the same
j = 1: the three values are the same
j = 0: the three values are the same

return the three values.

We have to find min first and a max after such that max - min = maxprofit .This can be done in O(n). while traversing start with first price as min, keep going forward , if you find a lower number then update min. If you find higher number than min, update max and maxprofit using curent min and max. whenever u find a new min after a max has been identified then update the min and reset the max. repeat. always update maxprofit any better poitns are found. this should work for all cases . (assuming prices are not -ve ofcourse)

case of 15,25,10,30. ans shud be 10,30

Lets the price process is N{1,...n}
create another array M{1,...,n-1} where M[i] is the maximum element in array N[i+1,...,n]; require O(n)
calculate max(M[i]-N[i]) where i start with 1 and end at n-1
and output this max.
complexity O(n)+O(n)

Use a sliding window of x < N days. Calculate mean of these prices and then with each day slide the window to right by one i.e. take mean of next x numbers. If price is moving over the mean of last x days then buy and if it is going below that sell.

Profit[size] = {0}
Min{size] = {0}
profit[0] = 0;
Min[0] = price[0];
for ( i = 1; i < n; i++) {
   if (price[i] < Min[i-1]) {
      Min[i-1] = price[i];
   else {
      Min[i] = Min[i-1];
   }
   profit[i] = price[i] - Min[i];
}

int getProfit(int arr[], int len)
{
	int count = 0, profit = 0, buy_val = 0;

	for(int i=0;i<len;i++)
	{
		if(arr[i] <= arr[i+1])
		{
			buy_val += arr[i];
			count++;
		}
		else if(count)
		{
			count = count * arr[i];
			profit += (count - buy_val);
			count = 0;
			buy_val = 0;
		}
	}

	return profit;
}

1- Start from the end, and keep max
find Minima in the array
diff = max - min

- Move to next, if > max then repeat 1

Following the simplest solution I can think of:

public Integer findBestStockBuySellPointsSimple(List<Integer> list) {
		Integer currentMin, tempMin, currentMax, currentMaxProfit = 0;
		tempMin = currentMin = currentMax = list.get(0);
		
		for (Integer price : list) {
			if (price < tempMin) 
				tempMin = price;

			if (price - tempMin > currentMaxProfit) {
				currentMin = tempMin;
				currentMax = price;
                                currentMaxProfit = currentMax - currentMin;
			}
		}
		return currentMaxProfit;
	}

1 - Remember the last lowest price.
2 - If the difference to the current price is bigger than my last
maximum you got a new maximum profit.

public class BuySellProblem {

    /**
     * @param args
     */
    public static void main(String[] args) {

        int tempProfit=0;
        int commitProfit=0;
        int tempBuy=0;
        int tempSell=0;
        int commitBuy=0;
        int commitSell=0;

        int[] input = {110 ,149 ,137, 147, 148, 151, 100};

        for (int i = 0,j=1; j < input.length; i++,j++) {


            int tempDiff=input[j]-input[i];

            if(tempDiff>0)
            {
                tempProfit=tempProfit+tempDiff;
                if(tempBuy==0){
                    tempBuy=input[i];
                }
                if(tempBuy>input[i]){
                    tempBuy=input[i];
                }
                tempSell=input[j];
                if(commitProfit==0 &&commitBuy==0&&commitSell==0){
                    commitProfit=tempProfit;
                    commitBuy=tempBuy;
                    commitSell=tempSell;
                    }
                if(commitBuy>tempBuy&&commitSell<tempSell)
                {
                    commitBuy=tempBuy;

                }

               if( commitSell<tempSell)
               {
                   commitSell=tempSell;
                   commitProfit=tempSell-tempBuy;
               }


            }
            else
            {
                if(commitProfit==0 &&commitBuy==0&&commitSell==0){
                commitProfit=tempProfit;
                commitBuy=tempBuy;
                commitSell=tempSell;
                }
                  if(commitBuy>tempBuy&&commitSell<tempSell){
                        commitBuy=tempBuy;


                }
                if( commitSell<tempSell)
                {
                    commitSell=tempSell;
                    commitProfit=tempSell-tempBuy;
                }



                tempProfit=0;

            }

        }

        System.out.println("MaxBuy:"+commitBuy);
        System.out.println("MaxSell:"+commitSell);
        System.out.println("MaxProfit:"+commitProfit);



    }

}

O(n)

public static void printMaxRange(int[] a){ //Stock numbers increasing sell & buy
		
		int currMax = 0;
		int prevMax = Integer.MIN_VALUE;
		int start = 0;
		int end = 0;
		int prevElement = 0;
		for(int i = 0; i < a.length; i++){
			
			if(a[i] < prevElement){
				currMax = a[end] - a[start];
				if(currMax > prevMax){
					prevMax = currMax;
				}
				start = i;
				end = i;
			}
			else if(i == a.length-1 && a[i] > prevElement){
				currMax = a[i] - a[start];
				if(currMax > prevMax)
					prevMax = currMax;
				end = i;
			}
			else if(a[i] > prevElement){
				end = i; 
			}
			
			prevElement = a[i];
		}
		
		//prevMax = currMax;
		
		System.out.println("Max Profit : " + prevMax);
		System.out.println("Range Start : " + start);
		System.out.println("Range End : " + end);
	}

package com.walmart.careercup;

public class MaximizeStockProfit {
private static final long[] GIVEN_SAMPLE=new long[] {44,43,46,54,20,43,45,48,41,45,50};

public static void main(String[] args){
int currentIndexMin = 0;
int currentIndexMax = 0;
boolean lookForNewMax=false;
boolean lookForNewMin=true;
boolean captureData=false;

int minIndex=currentIndexMin;
int maxIndex=currentIndexMin;

int i=0;
while(i<GIVEN_SAMPLE.length){

boolean shouldIncrement=true;

if(lookForNewMax && (GIVEN_SAMPLE[i]>GIVEN_SAMPLE[currentIndexMax])){
currentIndexMax=i;

} else if( lookForNewMax && GIVEN_SAMPLE[i]<GIVEN_SAMPLE[currentIndexMax] ) {
lookForNewMin=true;
lookForNewMax=false;

captureData=true;
}

if(captureData || i==GIVEN_SAMPLE.length-1 ) {
if((GIVEN_SAMPLE[currentIndexMax] - GIVEN_SAMPLE[currentIndexMin] >GIVEN_SAMPLE[maxIndex] - GIVEN_SAMPLE[minIndex])
||
(GIVEN_SAMPLE[currentIndexMax] - GIVEN_SAMPLE[minIndex] >GIVEN_SAMPLE[maxIndex] - GIVEN_SAMPLE[minIndex])){
minIndex=(GIVEN_SAMPLE[currentIndexMin]<=GIVEN_SAMPLE[minIndex])? currentIndexMin:minIndex;
maxIndex=currentIndexMax;
}
captureData=false;
currentIndexMin=i;
}
if(lookForNewMin && GIVEN_SAMPLE[i]<GIVEN_SAMPLE[currentIndexMin]){
currentIndexMin=i;
} else if(lookForNewMin && GIVEN_SAMPLE[i]>GIVEN_SAMPLE[currentIndexMin] ) {
lookForNewMin=false;
lookForNewMax=true;
currentIndexMax=i;
shouldIncrement=false;
}
if(shouldIncrement) ++i;
}


if(GIVEN_SAMPLE[minIndex]<GIVEN_SAMPLE[maxIndex]){
System.out.println("Buy on day ["+(minIndex+1)+"] at price ["+GIVEN_SAMPLE[minIndex]+"], and sell on day ["+(maxIndex+1)+"] at price ["+GIVEN_SAMPLE[maxIndex]+"]");
} else {
System.out.println("You can't make money on this stock with long strategy. Try shorting it.");
}
}
}

package com.walmart.careercup;

public class MaximizeStockProfit {
	private static final long[] GIVEN_SAMPLE=new long[] {44,43,46,54,20,43,45,48,41,45,50};
	
	public static void main(String[] args){
		int currentIndexMin = 0;
		int currentIndexMax = 0;
		boolean lookForNewMax=false;
		boolean lookForNewMin=true;
		boolean captureData=false;
		
		int minIndex=currentIndexMin;
		int maxIndex=currentIndexMin;
		
		int i=0;
		while(i<GIVEN_SAMPLE.length){
			
			boolean shouldIncrement=true;
			
			if(lookForNewMax && (GIVEN_SAMPLE[i]>GIVEN_SAMPLE[currentIndexMax])){
				currentIndexMax=i;
									
			} else if( lookForNewMax && GIVEN_SAMPLE[i]<GIVEN_SAMPLE[currentIndexMax] ) {
				lookForNewMin=true;
				lookForNewMax=false;
				
				captureData=true;
			}
			
			if(captureData  || i==GIVEN_SAMPLE.length-1 ) {
				if((GIVEN_SAMPLE[currentIndexMax] - GIVEN_SAMPLE[currentIndexMin] >GIVEN_SAMPLE[maxIndex] - GIVEN_SAMPLE[minIndex]) 
				||
				(GIVEN_SAMPLE[currentIndexMax] - GIVEN_SAMPLE[minIndex] >GIVEN_SAMPLE[maxIndex] - GIVEN_SAMPLE[minIndex])){
					minIndex=(GIVEN_SAMPLE[currentIndexMin]<=GIVEN_SAMPLE[minIndex])? currentIndexMin:minIndex;
					maxIndex=currentIndexMax;
				} 
				captureData=false;
				currentIndexMin=i;
			}
			if(lookForNewMin && GIVEN_SAMPLE[i]<GIVEN_SAMPLE[currentIndexMin]){
				currentIndexMin=i;
			} else if(lookForNewMin && GIVEN_SAMPLE[i]>GIVEN_SAMPLE[currentIndexMin] ) {
					lookForNewMin=false;
					lookForNewMax=true;
					currentIndexMax=i;
					shouldIncrement=false;
			} 
			if(shouldIncrement) ++i;
		}
		
		
		if(GIVEN_SAMPLE[minIndex]<GIVEN_SAMPLE[maxIndex]){
			System.out.println("Buy on day ["+(minIndex+1)+"] at price ["+GIVEN_SAMPLE[minIndex]+"], and sell on day ["+(maxIndex+1)+"] at price ["+GIVEN_SAMPLE[maxIndex]+"]");
		} else {
			System.out.println("You can't make money on this stock with long strategy. Try shorting it.");
		}
	}
}

Time complexity O(n)