Objective: Given an array represents cost of a stock on each day. You are allowed to buy and sell the stock only once. Write an algorithm to maximize the profit in single buy and sell.

Example:

int[] prices = {200, 500, 1000, 700, 30, 400, 900, 400, 50};
Output: Maximum Profit: 870, buy date index: 4, sell date index: 6

Approach 1: Brute Force

Use two nested loops. Taking one element at a time, consider outer loop value as buying date index and compare it with the every element in the inner loop which will be considered as selling index date. Keep track of the maximum. This will be the maximum profit.

2. Task is to find out subarray which has the largest sum. So we need to find out the 2 date indexes (left index and right index) between which the profit is maximum.

3. Divide the problem into 2 parts, left half and right half.

Now we can conclude the final result will be in one of the three possibilities.

Left half of the array. (Buy date index and sell date index both are in left half of the array).

Right half of the array. (Buy date index and sell date index both are in right half of the array).

Result will cross the middle of the array. (Buy date index in the and left half of the array and sell date index in right half of the array).

Solve the all three and return the maximum among them.

Left half and right half of the array will be solved recursively.

Maintain an object to keep track of profit and date indexes.

Time Complexity: O(nlogn)

Code:

Approach 3: Dynamic Programming

Iterate through last date index to start date index.

Keep track of the maximum stock price seen during iteration, say it is max_sell_price and current_profit.

For any i-th day, there are only two possibilities –

Either price on the i-th day is greater than max_sell_price, in that case update the max_sell_price with that price.

Else (price on the i-th day is less than max_sell_price) so it means current day can be considered as buying date so calculate the difference and compare it with the current_profit, if current_profit is less update it with the new value.

After the iteration, return current_profit.

See the code for more understanding.

Time Complexity: O(n)

Code:

Output:

Maximum Profit(DP): 870, buy date index: 4, sell date index: 6

__________________________________________________ Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________