CareerCup

Algorithm:
Dynamic Programing : o(n)
1.for each kth element keep the best pair values and minimum value
2.for k+1 element compare with (k+1, minmum) vs (best pair) and accordingly update the minimum and best pair values

what would be the approach if we were allowed to buy & sell any number of times
eg 5 1 4 6 7 8 4 3 7 9
Buy at 1 ,sell at 7
then Buy at 3 sell at 9
Net profit=12

There is a very simple solution in O(n). The max benefit is the case where you buy at the lowest price and sell at the highest, with the condition that the buy has to be before sell.

public static int getMaxBenefit(int []S) {
	int maxBenefit = 0;
	int minPrice = Integer.MAX_VALUE;
		
	for (int i = 0; i < S.length; i++) {
		maxBenefit = Math.max(maxBenefit, S[i] - minPrice);
		minPrice = Math.min(S[i], minPrice);
	}
		
	return maxBenefit;
}

construct two arrays as follow:
F(i)= min(0<x<i)
G(i) = max(i<x<10)
where i [0,10)
so u will get for your test case

F = 5 1 1 1 1 1 1 1 1 1
G = 9 9 9 9 9 9 9 9 9 9

take the difference as follow
diff(i) = G(i+1) - H(i)

and take the max of it
answer = 9-1 = 8

your examples is simple
a good test case should be 8 9 11 12 7 6 4 9 1 4

F = 8 8 8 8 7 6 4 4 1 1
G = 12 12 12 12 9 9 9 9 4 4

diffence
: 4 4 4 1 2 3 5 0 3
so the answer is 5
which you can verify

find the local maxima and minima of the given array for n elements..:)

int max_benefit = INT_MIN;
for(size_t i = 0; i < prices.size(); ++i)
{
	for(size_t j = i + 1; j < prices.size(); ++j)
	{
		if(prices[j] - prices[i] > max_benefit)
		{
			max_benefit = prices[j] - prices[i];	
		}
	}
}

This is O(n^2). Too lazy to figure out something more efficient

This should work in O(n).

#include <stdlib.h>
#include <stdio.h>

int * bestDates(int *prices, int length);

int main(){

  int dateArray[] = {-1, 1, 4, 6, 7, 8, 4, 3, 7, 9, 1, 2, 0, 12};
  int *returnDates = bestDates(dateArray, 15);
  if(!returnDates){
    printf("Error\n");
    return 0;
  }else{
    printf("Best Dates:\n");
    printf("Buy: %d\n", returnDates[0]);
    printf("Sell: %d\n", returnDates[1]);
  }
  return 0;
}


int * bestDates(int *prices, int length){
  if(prices == NULL || length < 2){
    return NULL; //error
  }

  int bestBuyDate = 0; // intialize with first day
  int bestSellDate = 1; // intialize with second day
  int smallestDate = (prices[0] <= prices[1])?0:1; // initialize with smaller of both days

  for(int i = 2; i < length; ++i) {

    if( (prices[i] - prices[smallestDate]) > (prices[bestSellDate] - prices[bestBuyDate]) ){
      //Better dates found
      bestSellDate = i;
      bestBuyDate = smallestDate; //smallest was best with this sell date
    }

    if( prices[i] < prices[smallestDate] ){
      //New smallest item found
      smallestDate = i;
    }
  }
  int * bestReturn = malloc(sizeof(int) * 2);
  if(bestReturn == NULL) return NULL; //error
  bestReturn[0] = prices[bestBuyDate];
  bestReturn[1] = prices[bestSellDate];
  return bestReturn;
}

Build a max heap and min heap data structure which only takes O(n) time (use heapify method). Once done look out the min element and maximum elements in both the heaps . the difference between these value is the answer

Build a max heap and min heap data structure which only takes O(n) time (use heapify method). Once done look out the min element and maximum elements in both the heaps which takes only O(1) time. the difference between these value is the answer

Without using Extra memory and in O(n) it's possible
Ex : 5 3 4 6 2 8 4 1 7 9
Calculate the difference with minimum, If the difference becomes -Ve, Change the minimum to index where you are getting -Ve calue.
-4 1 3 -1 6 2 -1 6 7

public class HelloWorld{

public static void main(String []args){
int val[]={10,14,15,19,12,115,14};

int min=val[0];int diff=0;
for (int i: val)
//System.out.println(i);
{
if(i<=min)min=i;
else diff=(i-min)>diff?i-min:diff;
}
System.out.println(diff);
}}

why not buy at 1,sell at 8 then again buy at 3 and sell at 9?
here max profit will be = 13

public static void getMaxProfit(int[] data) 
	{
		int len = data.length;
		int profit = Integer.MIN_VALUE;
		int s = 0; // sell index
		int b = 0; // buy index
		
		for(int i = 1; i < len; i++)
		{
			if (data[b] > data[i]) // minimizing the buy value
			{
				b = i;
			}
			
			if (data[s] < data[i]) // maximizing the sell value
			{
				s = i;
			}
			// updating the profit if sell index if greater than buy index
			if (s > b && profit < (data[s] - data[b])) 
			{
				profit = data[s] - data[b];
			}
		}
		
		System.out.println("Profit :" + profit);

}

Time complexity : O(1)
Straight forward and easy to understand.
Please point out any issue if you get.

By mistake Time complexity is written as O(1)
It will be O(n).

#include<stdio.h>
void stock(int a[])
{
int cmin=a[0],i,gmin=a[0],gmax=a[0],gd=0;

for(i=1;i<6;i++)
{ if(cmin>a[i])
cmin= a[i];
else if (gd<(a[i]-cmin)){
gmin=cmin;
gmax=a[i];
gd=a[i]-cmin;
}}
printf("%d -%d = %d",gmax,gmin,gd);

}
main(){
int arr[6]={2,5,1,3,2,2};
stock(arr);
}

They are essentially interested in a case where the difference between the two value is maximum. These values are all positive. So, the difference between the maximum and the minimum is the answer! All we need to do is to find these max and min. They can be found in O(n). Please correct me if I didn't get the question right.