CareerCup

bool findMinMax(int *array, int len, int * min, int * max)
{
int minIndex = 0, maxIndex = 0, curIndex = 0;
if (len > 0)
{
for (; curIndex < len; curIndex++)
{
if (array[curIndex] < array[minIndex])
{ // found a new minimum, so old max isnt valid anymore
minIndex = maxIndex = curIndex;
}
if (array[curIndex] > array[maxIndex])
{ // found new max
maxIndex = curIndex;
}
}
if (minIndex < maxIndex)
{ // return min & max
*min = array[minIndex];
*max = array[maxIndex];
return true;
}
}

return false;
}

Here is my version. complexity is O(n). coded in java.

public static void searchBestTrade( int[] price ) {
        int lowest = price[0];
        int highest = price[0];
        int buy = price[0];
        int sell = price[0];
        for(int i = 1; i < price.length; i ++) {
            if(price[i] > highest) {
                highest = price[i];
            } else if (price[i] < lowest) {
                lowest = price[i];
                highest = price[i]; 
            }
            // update trade record
            if(sell - buy < highest - lowest) {
                buy = lowest;
                sell = highest;
            }
        }
        System.out.println("Buy: " + buy + " / Sell: " + sell);
    }

Its simply maximum single sell profit algorithm,
Steps:
1) maxDiff = 0, currentMinimum = a[0]
2) for i in [0,n-1] do: 
curMinimum = min(curMinimum, a[i])
maxDiff = max(maxDiff, a[i] - curMinimum) 

3) maxDiff is the answer
Complexity = O(n)
working code:
public int[] getIndexIandJ(int[] integers){
        if(integers == null || integers.length == 1){
            return integers;
        }
        int maxDiff = 0;
        int curMin = integers[0];
        int startIndex = 0;
        int endIndex = 0;
        int tempStart = 0;
        for(int i = 1; i<integers.length; i++){
            if(curMin > integers[i]){
                curMin = integers[i];
                tempStart = i;
            }

            if (maxDiff < (integers[i] - curMin)){
                maxDiff = (integers[i] - curMin);
                startIndex = tempStart;
                endIndex = i;
            }
        }
        int[] indices = new int[2];
        indices[0] = startIndex;
        indices[1] = endIndex;
        return indices;
}

void find_max_profit(int array[], int n, int* min, int* max)
{
	int diff = 0;
	int m = array[n-1];
 	for(int i = n-2; i >= 0; i--)
	{
		if(array[i] >= m)
		{
			m = array[i];
		}
		else
		{
			if((m - array[i]) > diff)
			{
                 diff = m - array[i];
				*min = array[i];
				*max = m;
			}
		}
	}
}

I guess the easy way is to first sort the array (O(nlogn)), then pick the corresponding max and min elements (of course you need to make sure the max happens after the min) (O(n)). Consequently, the time complexity is still O(nlogn).

possible solution in O(n) complexity, without taking extra memory (just ~12 bytes).

void fund_better_points(unsigned* points, unsigned pointsLen, unsigned& p1, unsigned& p2)
{
unsigned currP1 = 0, currP2 = 0;
if(pointsLen) {
currP1 = currP2 = points[0];
}
p1 = p2 = currP1;
for(unsigned i=1; i<pointsLen; ++i) {
if(currP2 < points[i]) {
currP2 = points[i];
}
if(points[i] < currP1) {
if(((currP2 - currP1) > (p2 - p1)) ||
(((currP2 - currP1) == (p2 - p1)) && (currP1 < p1))) {
p2 = currP2;
p1 = currP1;
}
currP1 = currP2 = points[i];
}
}
if(((currP2 - currP1) > (p2 - p1)) ||
(((currP2 - currP1) == (p2 - p1)) && (currP1 < p1))) {
p2 = currP2;
p1 = currP1;
}
}

import java.util.Scanner;
class share
{
public static void main(String args[])
{
int in[] = new int[15];
int i,n,buy,sell;
Scanner s  = new Scanner(System.in);
System.out.println("Enter No of Inputs");
n = s.nextInt();
for(i=0;i<n;i++)
{
in[i] = s.nextInt();
}
buy = in[0];
sell = in[0];
for(i=1;i<n;i++)
{
if(in[i]>sell)
{sell=in[i];}
if(in[i]<buy)
{buy=in[i];}
} 
System.out.println("Buy:" + buy);
System.out.println("Sell:" + sell);
}
}

int find_Max_Profit(int array[], int n) {
  int minNum, maxProfit, curMax;
  minNum = INT_MAX;
  curMax = INT_MIN;
  for (int i = 0; i < n; i++ ) {
     if( array[i] > minNum) {
         minNum = array[i];
     }
     maxProfit = array[i] - minNum;
     if(maxProfit > curMax) {
          curMax = maxProfit;
     }
   }
   return curMax;
}

simple one,
--> find the largest element in array after the current element
--> now do largest element minus current element.
--> do this for all array elements.

for eg1,
    given array        		[30, 12,  15,  10,  40,  30,  60, 100]
    next_max_elt    		[100, 100,  100,  100, 100,  100,  100, 0    ]

    difference array		[70,    88,    85,    90,    60,    70,    40,   -100]
-> here the maximum difference is 90.
-> so when we buy at 10 and sell at 100 , we get more profit.

example 2:

    price_array			[8,	22,	12,	9,	6,	10,	11,	13,	20,	18,	4,	19]
    next_max_elt		[22,  0,	20,	20,	20,	20,	20,	13,	0,	19,	19,	0]

    difference_array         [14,	-22,	8,	11,	14,	10,	9,	7,	-20,	1,	15,	-19]
-> maximum value is 15,
-> so we have to buy at 4 and sell at  	19.

solution :
for ex : a[]={30, 12, 15, 10, 40, 30, 60, 100} (given prices of share)
prepare an auxillary array aux[i]=a[i+1]-a[i]
aux[]={-18,3,-5,30,-10,30,40}
and find start and end index for max sum sub vector in aux[]....(a[start] , a[end+1] ) is required solution(apply kadane's algorithms on aux[])

and code for this is

#include<stdio.h>



/*-----------------------------maximum sum subarray(Kadane's algorithm)-------------------------------*/

void maxsum(int *a,int n){

int max_so_far=a[0],max_end_here=a[0];
int start,end,temp_start,i;

for(i=0;i<n;i++){
	if(max_end_here<0){
		max_end_here=a[i];
		temp_start=i;	

	}
	else
		max_end_here += a[i];

	if(max_end_here>max_so_far){
		max_so_far=max_end_here;
		start=temp_start;
		end=i;
		
	}

}

printf("( %d , %d )  %d",start,end+1,max_so_far);

return;
}


/*-----------------------------max profit share problem-------------*/


void share(int *a,int n){

int aux[n-1],i;

for(i=0;i<n-1;i++)
	aux[i]=a[i+1]-a[i];

maxsum(aux,n-1);

}



void main(){

int a[10]={30,12,15,5,40,30,60,130,2,110 };
share(a,10);

}

Check out the Kim-Shan Algorithm.

algo: subtract all the elements with next elements as shown below and once you get that then basically what we are looking for is a maximum subarray which can be find out using kadence algorithm.
//int a[] = {30, 12, 15, 10, 40, 30, 60, 100};
int a[] = {-18, 3, -5, 30, -10, 30, 40};

static int l_index = 0, h_index = 0;

int maximum_subarray(int* nums, int start_index, int end_index)
{
        int max_sum = 0;
        int cur_index, cur_sum = 0, max_ending_here, max_so_far;

        for(cur_index = 0; cur_index < end_index; cur_index++) {
                cur_sum = cur_sum + nums[cur_index];
                if(cur_sum < 0) {
                        cur_sum = 0;
                        l_index = cur_index;
                }
                if(cur_sum > max_sum) {
                        max_sum = cur_sum;
                        h_index = cur_index;
                }
        }
        return max_sum;
}

int main()
{
        //int a[] = {30, 12, 15, 10, 40, 30, 60, 100};
        int a[] = {-18, 3, -5, 30, -10, 30, 40};
        printf("sum %d\n", maximum_subarray(a, 0, sizeof(a)/sizeof(a[0])));
        printf("left %d right %d\n", l_index, h_index);
        return 0;
}

Here is my version. complexity is O(n). coded in java.

{{
public static void searchBestTrade( int[] price ) {
int lowest = price[0];
int highest = price[0];
int buy = price[0];
int sell = price[0];
for(int i = 1; i < price.length; i ++) {
if(price[i] > highest) {
highest = price[i];
} else if (price[i] < lowest) {
lowest = price[i];
highest = price[i];
}
// update trade record
if(sell - buy < highest - lowest) {
buy = lowest;
sell = highest;
}
}
System.out.println("Buy: " + buy + " / Sell: " + sell);
}
}}

#include <cstdio>

using namespace std;
void getMax(int& _buy, int& _sell, int n, int price[])
{
    int buy = price[0];
    int sell = price[1] - price[0];
    for(int i = 2; i < n; i++)
    {
        buy = price[i - 1] < buy ? price[i - 1] : buy;
        if(price[i] - buy > sell)
        {
            _buy = buy;
            _sell = price[i];
            sell = price[i] - buy;
        }
    }
}

int main()
{
    int n = 0;
    int a[100];
    int buy = 0, sell = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    getMax(buy, sell, n, a);
    printf("%d %d\n", buy, sell);
    return 0;
}

int main()
{
int temp[5]={2,7,66,9,3};
int i=0;
int curmin,curmax;
curmin=curmax=temp[0];
for(;i<5;i++)
{
if(curmin>temp[i])
curmin=temp[i];
if(curmax<temp[i])
curmax=temp[i];
}
printf("%d\n",curmax);
printf("%d\n",curmin);




getch();
}

public static void bestTrade(int[] prices)
	{
		if (prices == null || prices.length < 2)
		{
			return;
		}
		int min = prices[0];
		int buy = min;
		int sell = buy;
		for(int price : prices)
		{
			if (price < min)		
			{
				min = price;
			}
			else if (price > sell)	
			{
				sell = price;
				buy = min;
			}			
		}
		System.out.println("Buy: " + buy + "\nSell: " + sell);
	}

Java code::
public static void searchBestTrade( int[] price ) {
Arrays.sort(price);
System.out.println("Buy: " + price[0]+ " / Sell: " + price[price.length - 1]);
}

Simple way here in perl.

#########################
#!/usr/bin/perl
my $input = “30,12,15,10,40,30,60,100”;

my @array = split (/\,/, $input);

my @sort_array = sort {$a <=> $b} @array;

print “Best BUY : $sort_array[0] and Best SELL: $sort_array[$#sort_array] \n”;

#####################################

void findMaxProfit(){
                int[] share= new int[]{30, 12, 15, 5, 40, 30, 60, 130, 2, 110 };
		int maxProfit=0;
		int buy=share[0];
		int sell=share[0];
		int lowest=share[0],heighest=share[0];
		boolean isLowestPriceChanged=false;
		
		for (int i = 1; i < share.length; i++) {
			if(lowest>share[i]){
				lowest=share[i];
				isLowestPriceChanged=true;
			}
			
			 if(heighest<share[i] || isLowestPriceChanged){
				heighest=share[i];
				isLowestPriceChanged=false;
			}
			
			if(heighest-lowest>maxProfit){
				maxProfit=heighest-lowest;
				buy=lowest; sell=heighest;
				System.out.println("buy "+ buy +" sell "+sell);
				
			}
			
		}
		
		System.out.println("buy "+ buy +" sell "+sell);

	}

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String string = br.readLine();
String[] integers = string.split(",");
int[] input = new int[integers.length];
for (int count = 0; count < integers.length; count++) {
input[count] = Integer.parseInt(integers[count]);
}
HashMap<Integer, Integer> positionMap = new HashMap<Integer, Integer>();
for (int count = 0; count < integers.length; count++) {
if (positionMap.get(input[count]) == null) {
positionMap.put(input[count], count);
}
}
int maxProfit = Integer.MIN_VALUE;
Arrays.sort(input);
int buyValue = 0;
int saleValue = 0;
int i = 0;
int j = input.length - 1;
while (i <= j) {
if (positionMap.get(input[j]) > positionMap.get(input[i])
&& ((input[j] - input[i]) > maxProfit)) {
buyValue = input[i];
saleValue = input[j];
maxProfit = input[j] - input[i];
}
if (positionMap.get(input[j - 1]) > positionMap.get(input[i])
&& ((input[j - 1] - input[i]) > maxProfit)) {
buyValue = input[i];
saleValue = input[j - 1];
maxProfit = input[j - 1] - input[i];
}
if (positionMap.get(input[j]) > positionMap.get(input[i + 1])
&& ((input[j] - input[i + 1]) > maxProfit)) {
buyValue = input[i + 1];
saleValue = input[j];
maxProfit = input[j] - input[i + 1];
}
j--;
i++;
}
// System.out.println("StockPrize By value : " + buyValue
// + " StockPrice sale value : " + saleValue
// + " Maximum Profit : " + maxProfit);
System.out.println(buyValue + "," + saleValue);

}

public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String string = br.readLine();
		String[] integers = string.split(",");
		int[] input = new int[integers.length];
		for (int count = 0; count < integers.length; count++) {
			input[count] = Integer.parseInt(integers[count]);
		}
		HashMap<Integer, Integer> positionMap = new HashMap<Integer, Integer>();
		for (int count = 0; count < integers.length; count++) {
			if (positionMap.get(input[count]) == null) {
				positionMap.put(input[count], count);
			}
		}
		int maxProfit = Integer.MIN_VALUE;
		Arrays.sort(input);
		int buyValue = 0;
		int saleValue = 0;
		int i = 0;
		int j = input.length - 1;
		while (i <= j) {
			if (positionMap.get(input[j]) > positionMap.get(input[i])
					&& ((input[j] - input[i]) > maxProfit)) {
				buyValue = input[i];
				saleValue = input[j];
				maxProfit = input[j] - input[i];
			}
			if (positionMap.get(input[j - 1]) > positionMap.get(input[i])
					&& ((input[j - 1] - input[i]) > maxProfit)) {
				buyValue = input[i];
				saleValue = input[j - 1];
				maxProfit = input[j - 1] - input[i];
			}
			if (positionMap.get(input[j]) > positionMap.get(input[i + 1])
					&& ((input[j] - input[i + 1]) > maxProfit)) {
				buyValue = input[i + 1];
				saleValue = input[j];
				maxProfit = input[j] - input[i + 1];
			}
			j--;
			i++;
		}
//		System.out.println("StockPrize By value : " + buyValue
//				+ " StockPrice sale value : " + saleValue
//				+ " Maximum Profit : " + maxProfit);
		System.out.println(buyValue + "," + saleValue);
		
	}

import java.util.Scanner;


public class ShareMarket {
public static void main(String a[])
{
Scanner sc = new Scanner(System.in);
String[] ins = sc.nextLine().split(" ");
int numEles = ins.length;
int[] in = new int[numEles];
int i = 0;
for(String s:ins)
{
in[i++] = Integer.parseInt(s);
}

int buy = in[0], sell = in[0], hp = 0;
int b = 0, s = 0;
for(i = 0 ; i < numEles; i++)
{
b = in[i];
for(int j = i + 1; j < numEles; j++)
{
s = in[j];
if( (s - b) > hp )
{
hp = s-b;
buy = b;
sell = s;
}
}
}
System.out.println(buy + " " + sell + " " + hp);
}
}

This solution follows this approach: -
- Since the highest price of the stock will be towards the end, parse the array from the right and mark the highest prices.
- Also, we need the max difference between the buying price (lower value, towards the beginning of the array) with the selling price.

- Create another array (diff) with same length as the prices array
- Parse the prices array from behind,
- If price is larger than the previous largest price
- Store -1 in the diff array.
- Change the largest price to this price.
- If price is lower than the largest price
- Store the diff between the 2 prices in the diff array

- Now parse the diff array from beginning to find the largest diff
- Once the largest diff is found, this is your buying price. Start a loop from this price to the end of the diff array
- As soon as you encounter a -1 in the diff array, this is your selling price

private static void printStockPrices(int[] prices) {
		long start = System.currentTimeMillis();
		int[] diff = new int[prices.length];
		int max_index = -1;
		int max_diff_index = 0;
		
		for (int j = prices.length - 1; j >= 0; j--) {
			if (j == prices.length - 1) {
				diff[j] = -1;
				max_index = j;
			} else if (prices[j] >= prices[max_index]) {
				diff[j] = -1;
				max_index = j;
			} else {
				diff[j] = prices[max_index] - prices[j];
			}
		}
		
		for (int j = 0; j < diff.length; j++) {
			if (diff[j] > diff[max_diff_index]) {
				max_diff_index = j;
			}
		}
		
		for (int j = max_diff_index + 1; j < diff.length; j++) {
			if (diff[j] == -1) {
				System.out.println ("(" + prices[max_diff_index] + ", " + prices[j] + ")");
				break;
			}
		}
		
		long end = System.currentTimeMillis();
		System.out.println ("Time taken (in sec): " + ((end - start)/1000));
	}