Problem

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

OR

Given an array of stock prices, where the increasing indexes of the array signify the increase in time. Return a good time to buy and sell such that profit is maximized. You are allowed to transact only once.

OR

Given an array A[], write an algorithm to find Maximum difference between two elements where larger element appears after the smaller element or in other words find A[i] and A[j] such that A[j]-A[i] is maximum where j > i.

Examples

Example 1:

Input:
prices = [7,1,5,3,6,4]
Output:
 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input:
prices = [7,6,4,3,1]
Output:
 0
Explanation: In this case, no transactions are done and the max profit = 0.

Solution

Method 1: Brute Force

This problem can be easily solved using two nested loops. Take each element at a time and compare it with all the other elements and keep the track of the maximum difference elements where larger element appears after the smaller element.

Code

Java
public int maxProfit(int[] prices) {
	int maxDiff = -1;
	for (int i = 0; i<prices.length; i++) {
		for (int j = i; j<prices.length; j++) {
			if (prices[j] > prices[i] && (prices[j] - prices[i] > maxDiff))
				maxDiff = A[j] - A[i];
		}
	}
	return maxDiff;
}

Time complexity is O(N^2).

Method 2: Divide and Conquer

  • We need to find the two elements A[i] and A[j] so that A[j] – A[i] is maximum and j > i

  • Divide the input array into 2 parts, left Half and right half.

  • We have divided the problem in 2 parts. Now we can conclude that for answer-

    • Both indexes i and j are in the left half of the array.
    • Both indexes i and j are in the right half of the array.
    • Index i is in left half and index j is in right half of the array.

  • Solve the above 3 sub problems recursively and final answer will the maximum of these 3 sub problems.

This solution is very much similar to Merge sort.

Complexity

Time complexity is O(nlogn).

Code

Java
public int maxProfit(int[] prices) {
	return maxProfit(prices, 0, prices.length - 1);
}

private int maxProfit(int[] prices, int start, int end) {
	if (start >= end) {
		return -1;
	}
	int mid = start + (end - start) / 2;
	
	int leftDiff = maxProfit(prices, start, mid);
	int rightDiff = maxProfit(prices, mid + 1, end);
	
	int minLeft = getMin(prices, start, mid);
	int maxRight = getMax(prices, mid, end);
	
	int centerDiff = maxRight - minLeft;
	
	return Math.max(centerDiff, Math.max(leftDiff, rightDiff));
}

public int getMin(int[] nums, int i, int j) {
	int min = nums[i];
	for (int k = i + 1; k<= j; k++) {
		if (nums[k]<min)
			min = nums[k];
	}
	return min;
}
public int getMax(int[] nums, int i, int j) {
	int max = nums[i];
	for (int k = i + 1; k<= j; k++) {
		if (nums[k] > max)
			max = nums[k];
	}
	return max;
}

Method 3 - Kadane - Tracking Diff with Min Element so Far

In this method, instead of taking difference of the picked element with every other element, we take the difference with the minimum element found so far. So we need to keep track of 2 things:

  1. Maximum difference found so far (max_diff).
  2. Minimum number visited so far (min_element)

Code

Java
public int maxProfit(int prices[]) {
	int maxProfit = Integer.MIN_VALUE;
	int minElement = prices[0];
	int i;
	for (i = 1; i<prices.length; i++) {
		if (prices[i] - minElement > max_diff)
			maxProfit = prices[i] - minElement;
		if (prices[i]<minElement)
			minElement = prices[i];
	}
	return maxProfit;
}

Removing if condition:

public int maxProfit(int[] prices) {
	if (prices == null || prices.length<= 1) {
		return 0;
	}

	int min = prices[0]; // min so far
	int ans = 0;

	for (int i = 1; i<prices.length; i++) {
		ans = Math.max(result, prices[i] - min);
		min = Math.min(min, prices[i]);
	}

	return ans;
}

Complexity

Time Complexity: O(n), Auxiliary Space: O(1)

Method 4 - Kadane - Tracking Diff with Max Element so Far

Previous solution was on min_so_far, now we have max_so_far.

  • Traverse the array from right to left.
  • Maintain 2 variables – maxDifference (this will be our final answer), and max_so_far(maximum element we encounter while traversing the array)
  • During iteration, every element has 2 choices
    • Either current element is the maximum element among elements which are iterated, if yes then max_so_far = current element.
    • OR current element is less than the max_so_far. If yes then update the maxDifference = max_so_far – current element.
  • Once the iteration is done, return maxDifference.

Complexity

Time complexity: O(n), Space complexity: O(1)

Code

Java
 public static int maxDifference(int[] A) {
 	int size = A.length;
 	int maxDiff = -1;
 	int max_so_far = A[size - 1]; //assign the last element
 	for (int i = size - 2; i > 0; i--) {
 		if (max_so_far<A[i])
 			max_so_far = A[i];
 		else if (max_so_far > A[i])
 			maxDiff = Math.max(maxDiff, max_so_far - A[i]);
 	}
 	return maxDiff;
 }

Complexity

Time Complexity: O(n), Auxiliary Space: O(1)

Method 5 - Dynamic Programming - Max Sum Subarray

First find the difference between the adjacent elements of the array and store all differences in an auxiliary array diff[] of size n-1. Now this problems turns into finding the maximum sum subarray of this difference array.

Code

Java
int maxProfit(int prices[],) {
	// Create a diff array of size n-1. The array will 
	// hold the difference of adjacent elements
	int diff[] = new int[n - 1];
	for (int i = 0; i<n - 1; i++) {
		diff[i] = arr[i + 1] - arr[i];
	}

	// Now find the maximum sum subarray in diff array
	int maxDiff = diff[0];
	for (int i = 1; i<n - 1; i++) {
		if (diff[i - 1] > 0) {
			diff[i] += diff[i - 1];
		}
		if (maxDiff<diff[i]) {
			maxDiff = diff[i];
		}
	}
	return maxDiff;
}

Method 6 - 2 Pointer Approach

Code

Java
int maxDiff(int arr[]) {
	int l = 0, r = 1; // left buy, right sell
	int maxProfit = 0;
	while(r < arr.length) {
		// is profitable transaction?
		if(price[l] < price[r]){
			int profit = price[r] - price[l]
			maxProfit = Math.max(profit, maxProfit);
		}else {
			l = r;
		}
		r++;
	}
}

Complexity

Time Complexity: O(n), Auxiliary Space: O(1)