CareerCup

public static void main(String[] args){
        int[] data = {5,9,6,2,4,8,3,1};
        
        int diff = 0;
        
        int min = data[0];
        
        for (int i=0; i < data.length; i++){
            //get min
            if (data[i] < min){
                min = data[i];
            }
            
            int tempDiff = data[i] - min;
            
            if (tempDiff > diff){
                diff = tempDiff;
            }
            
        }
        
        System.out.println(diff);
    }

int FindMaxProfit(std::vector<int> prices)
{
	if(prices.size()<2) return 0;

	/* Find minimum and maximum values in given list */
	int min = prices.front(), max = prices.front(), minIndx = -1, maxIndx = -1;
	for(int i=0; i<prices.size(); i++)
	{
		if(prices[i]<=min)
		{
			min = prices[i];
			minIndx = i;
		}
		if(prices[i]>=max)
		{
			max = prices[i];
			maxIndx = i;
		}
	}

	/* If the minimum is on left side of the maximum value, maxProfit = max - min */
	if(minIndx<maxIndx)
		return max-min;
	else
	{
		/* Otherwise divid the list into two lists, begin to max and max+1 to end, and repeat this function on both. Max of both is the answer*/
		std::vector<int> leftVector, rightVector;
		leftVector.assign(prices.begin(), prices.begin()+maxIndx+1);
		rightVector.assign(prices.begin()+maxIndx+1, prices.end());
		int leftHalfMaxProfit = FindMaxProfit(leftVector);
		int rightHalfMaxProfit = FindMaxProfit(rightVector);
		return (leftHalfMaxProfit>rightHalfMaxProfit ? leftHalfMaxProfit : rightHalfMaxProfit);
	}
};

I would imagine we code it like how a human would find the answer if given a "chart" of a stock price.

I would think selling at any point in time t=T would be maximixed if we had bought the stock at the minimum price seen before that point.

So as you go along left to right in the array, keep track of the minimum stock price seen so far, and check what profit we would have gotten selling at the current time t (current element in array). And keep track of the maximum such profit seen so far.


pseudocode:
min_seen = A[0] //minimum seen in all previous time steps before
max_profit= 0

for time t = 1 to n-1; // 0 indexed arrray, need only start at 1 if exists
{
if ( A[t] - min > max_profit ) // if selling now gives greater profit
max_profit = A[t] - min;

if( A[t] < min ) // if current stock price is below min. seen before now
min = A[t]
}

#include <iostream>
#include <limits>
using namespace std;

int main() {

	const unsigned int MAX_VALUES = 8;

	int data[MAX_VALUES] = {5,9,6,2,4,8,3,1};
	int maxProfit = std::numeric_limits<int>::min(); //Negative Infinite!

	for (int buy = 0 ; buy < MAX_VALUES ; buy++) {
		for (int sell = buy ; sell < MAX_VALUES ; sell++) {
			if (data[sell] - data[buy] > maxProfit)
				maxProfit = data[sell] - data[buy];
		}
	}

	cout << "Most is :" << maxProfit << endl;
	cin >> maxProfit;

	return 0;
}

#include <iostream>
#include <limits>
using namespace std;

int main() {

	const unsigned int MAX_VALUES = 8;

	int data[MAX_VALUES] = {5,9,6,2,4,8,3,1};
	int maxProfit = std::numeric_limits<int>::min(); //Negative Infinite!

	for (int buy = 0 ; buy < MAX_VALUES ; buy++) {
		for (int sell = buy ; sell < MAX_VALUES ; sell++) {
			if (data[sell] - data[buy] > maxProfit)
				maxProfit = data[sell] - data[buy];
		}
	}

	cout << "Most is :" << maxProfit << endl;
	cin >> maxProfit;

	return 0;
}

Just to note: when I saw this question, I recalled that CLR use this problem as the basis for introducing the Maximum Subarray Problem, but as Dennis's answer shows a straightforward solution is possible without getting into all that.

//Fastest way to do it using recursive function

public class MaxProfit {
public static void main(String[] args){
int[] data = {5,9,6,2,4,8,3,1};
System.out.println(maxProfit(data, data.length -1, 0));
}
static int maxProfit(int[] data, int curIndex, int prevMax){
if (curIndex == 0) {
return prevMax;
}
if (curIndex == data.length - 1){
return maxProfit(data, curIndex -1, data[curIndex-1]-data[curIndex]);
}else{
return maxProfit(data, curIndex -1, Math.max(data[curIndex]-data[curIndex - 1], data[curIndex]-data[curIndex - 1] + prevMax ));

}

}
}

//Fastest way to do it using recursive function

public class MaxProfit {
public static void main(String[] args){
int[] data = {5,9,6,2,4,8,3,1};
System.out.println(maxProfit(data, data.length -1, 0));
}
static int maxProfit(int[] data, int curIndex, int prevMax){
if (curIndex == 0) {
return prevMax;
}
if (curIndex == data.length - 1){
return maxProfit(data, curIndex -1, data[curIndex-1]-data[curIndex]);
}else{
return maxProfit(data, curIndex -1, Math.max(data[curIndex]-data[curIndex - 1], data[curIndex]-data[curIndex - 1] + prevMax ));

}

}
}

int i=0, j=0, itemp=0, jtemp=0, k=0, max=0

for (k = 1; k<sizeof(stockarray); k++)
{if (stockarray[k] > stockarray[itemp] )
{jtemp=k;
}
else {itemp=k; jtemp=k;}

if ((stockarray[jtemp] - stockarray[itemp]) > max)
{max = stockarray[jtemp] - stockarray[itemp];
i = itemp;
j=jtemp;
}

}

cout<<"the max profit is " <<max <<endl;
cout<< " the buying price is " << stockarray[i] <<endl;
cout<< "the selling price is" <<stockarray[j]<<endl;

public static void maxProfit(int arr[]) {
        if (arr.length <= 1) {
            return;
        }

        int min = arr[0];
        int iMin = arr[0];
        int minIndex = 0;
        int max = arr[0];
        int iMax = arr[0];
        int tempMax = 0;
        int maxIndex = 0;

        for (int i = 1; i < arr.length; i++) {
            if ((max-min) < (arr[i]-min) && minIndex < i) {
                max = arr[i];
                maxIndex = i;
                if(tempMax<(max-min))
                {
                    iMin = min;
                    iMax = max;
                    tempMax = max-min;
                }
                continue;
            }
            if (min > arr[i]) {
                min = arr[i];
                max = arr[i];
                maxIndex = i;
                minIndex = i;
            }
        }
        System.out.println(iMin + " " + iMax);
    }

public class maximumProblem {
	
	public static void main(String args[]){	
		int[] ip ={5,	9,	6,	2,	4,	8,	3,	1};
		int[] iparr = new int[ip.length-1];
		int max = 0, left = 0,right = 0,sum=0,i,j = 0;
		for(i = 0;i<ip.length-1;i++){
			iparr[i] = ip[i+1] - ip[i];
		}	
		System.out.println(" ");
		for(i =0;i<iparr.length;i++){
			for(j = i;j<iparr.length;j++){
				sum = sum +iparr[j];
				if(sum > max){
				max = sum;
				left = i+1;
				right = j+1;
				}
			}
			sum = 0;
		}
		System.out.println("Profit is :"+max+"\nFrom Day: "+left+ " To Day: " +right);
	}
}

public static void maximizingProfit() {
    int[] data = {5,9,6,2,4,8,3,1};
    
    int maxProfit = 0;
    int finalSp = 0;
    int finalCp = 0;
    for (int i = 1 ; i < data.length; ++i ) {
      // selling at time 'i' will make a maximum profit of:
      int sp = data[i];
      for ( int j = i-1 ; j >= 0 ; --j ) {
        int cp = data[j];
        int profit = sp - cp;
        if (maxProfit < profit) {
          maxProfit = profit;
          finalSp = data[i];
          finalCp = data[j];
        }
      }
    }
    System.out.println("Max profit: " + (finalSp - finalCp) + ". Selling " + finalSp + " buying: " + finalCp);
    
  }

int[] stockPrice={1,2,3,4,0};

		int min=0,max=0,profit = 0;
		
		for(int i=0;i<stockPrice.length;i++){
			for(int j=i+1;j<stockPrice.length;j++){
				if(stockPrice[j]-stockPrice[i]>profit){
					min=i;
					max=j;
					profit=stockPrice[j]-stockPrice[i];
				}
			}
		}
		System.out.println(stockPrice[min]+" ,"+stockPrice[max]+" profit:"+profit);

Here is a Recursive version:

...
void FindMaxProfit( int a[], int n, int *mp )
{
	if( --n == 0 )
		return;
	FindMaxProfit( &a[1], n, mp );
	int mp2 = a[1] - a[0];
	if( mp2 > *mp )
		*mp = mp2;
}
...
	int a[] = { 5, 9, 6, 2, 4, 8, 3, 1 };
	int n = 8;
	int mp = 0;
	FindMaxProfit( &a[0], n, &mp );
	cout << "Max Profit: " << mp << endl;
...

Output:
4

{{
package alex;

public class MaxDiff {

public static void maxDiff(int[] a) {
if (a.length < 2) return;

int end = a.length - 1;
int min = a[0];
int maxDiff = 0;

for (int i = 1; i < end; i++) {
if (a[i] < min) {
min = a[i];
} else {
int diff = a[i] - min;
if (diff > maxDiff) {
maxDiff = diff;
}
}
}

int diff = a[end] - min;
if (diff > maxDiff) {
maxDiff = diff;
}

System.out.println("maxDiff = " + maxDiff);
}


//v1 loop; mark min along the way
public static void main(String[] args) {
int[] a = {5,9,6,2,4,8,3,1}; //{1,3,6,4,2,7,-1};
MaxDiff.maxDiff(a);
}

}
}}

#include <iostream>

using namespace std;

int max(int a, int b)
{return a>b? a:b;}

int maxProfit(int price[], int n)
{
// Create profit array and initialize it as 0
int *profit = new int[n];
for (int i=0; i<n; i++)
profit[i] = 0;

/* Get the maximum profit with only one transaction
allowed. After this loop, profit[i] contains maximum
profit from price[i..n-1] using at most one trans. */
int max_price = price[n-1];
for (int i=n-2;i>=0;i--)
{
// max_price has maximum of price[i..n-1]
if (price[i] > max_price)
max_price = price[i];

// we can get profit[i] by taking maximum of:
// a) previous maximum, i.e., profit[i+1]
// b) profit by buying at price[i] and selling at
// max_price
profit[i] = max(profit[i+1], max_price-price[i]);
}

int max = profit[0];

for (int i=0; i<n; i++)
if (max < profit[i])
max = profit[i];

return max;
}


int main()
{
int price[] = {2, 30, 15, 10, 8, 25, 80};
int n = sizeof(price)/sizeof(price[0]);
cout << "Maximum Profit = " << maxProfit(price, n);
return 0;
}