Be the first user to complete this post

  • 0
Add to List
Medium

552. Stock Single Sell Problem - Divide and Conquer

Objec­tiveGiven an array represents the 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 a single buy and sell.

Exam­ple:

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

Earlier we have seen the Dynamic programming solution, In this post we will discuss the divide and conquer approach

Divide and Conquer

  • The approach is quite similar to “Maximum Subarray Problem – Divide and Conquer
  • Task is to find out the 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.
  • Divide the problem into 2 parts, the left half and the right half.
  • Now we can conclude the final result will be in one of the three possibilities.
    1. The left half of the array. (Buy date index and sell date index both are in the left half of the array).
    2. The right half of the array. (Buy date index and sell date index both are in the right half of the array).
    3. The result will cross the middle of the array. (Buy date index in the left half of the array and sell date index in the right half of the array).
  • Solve all three and return the maximum among them.
  • The 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)




public class Main { public Result maxProfit(int [] prices, int start, int end){ if(start>=end){ return new Result(0,0,0); } int mid = start + (end-start)/2; Result leftResult = maxProfit(prices,start,mid); Result rightResult = maxProfit(prices,mid+1,end); int minLeftIndex = getMinIndex(prices, start, mid); int maxRightIndex = getMaxIndex(prices, mid, end); int centerProfit = prices[maxRightIndex] - prices[minLeftIndex]; if(centerProfit>leftResult.profit && centerProfit>rightResult.profit){ return new Result(centerProfit,minLeftIndex,maxRightIndex); }else if(leftResult.profit>centerProfit && rightResult.profit>centerProfit){ return leftResult; }else{ return rightResult; } } public int getMinIndex(int [] A, int i, int j){ int min = i; for (int k = i+1; k <=j ; k++) { if(A[k]<A[min]) min = k; } return min; } public int getMaxIndex(int [] A, int i, int j){ int max = i; for (int k = i+1; k <=j ; k++) { if(A[k]>A[max]) max = k; } return max; } public static void main(String[] args) { Main m = new Main(); int [] prices = { 200, 500, 1000, 700, 30, 400, 900, 400, 50}; int start = 0; int end = prices.length-1; Result result = m.maxProfit(prices,start,end); System.out.println("Maximum Profit(Divide & Conquer): " +result.profit + ", buy date index: " + result.buyDateIndex + ", sell date index: " + result.sellDateIndex); } } class Result{ int profit=0; int buyDateIndex=0; int sellDateIndex=0; public Result(int profit, int buyDateIndex, int sellDateIndex){ this.profit = profit; this.buyDateIndex = buyDateIndex; this.sellDateIndex = sellDateIndex; } }



class Result: def __init__(self, profit, buy_date_index, sell_date_index): self.profit = profit self.buy_date_index = buy_date_index self.sell_date_index = sell_date_index class Main: def max_profit(self, prices, start, end): if start >= end: return Result(0, 0, 0) mid = start + (end - start) // 2 left_result = self.max_profit(prices, start, mid) right_result = self.max_profit(prices, mid + 1, end) min_left_index = self.get_min_index(prices, start, mid) max_right_index = self.get_max_index(prices, mid, end) center_profit = prices[max_right_index] - prices[min_left_index] if center_profit > left_result.profit and center_profit > right_result.profit: return Result(center_profit, min_left_index, max_right_index) elif left_result.profit > center_profit and right_result.profit > center_profit: return left_result else: return right_result @staticmethod def get_min_index(prices, i, j): min_index = i for k in range(i + 1, j + 1): if prices[k] < prices[min_index]: min_index = k return min_index @staticmethod def get_max_index(prices, i, j): max_index = i for k in range(i + 1, j + 1): if prices[k] > prices[max_index]: max_index = k return max_index if __name__ == "__main__": m = Main() prices = [200, 500, 1000, 700, 30, 400, 900, 400, 50] start = 0 end = len(prices) - 1 result = m.max_profit(prices, start, end) print(f"Maximum Profit (Divide & Conquer): {result.profit}, buy date index: {result.buy_date_index}, sell date index: {result.sell_date_index}")



package main import ( "fmt" "math" ) type Result struct { Profit int BuyDateIndex int SellDateIndex int } type Main struct{} func (m *Main) maxProfit(prices []int, start, end int) Result { if start >= end { return Result{0, 0, 0} } mid := start + (end-start)/2 leftResult := m.maxProfit(prices, start, mid) rightResult := m.maxProfit(prices, mid+1, end) minLeftIndex := m.getMinIndex(prices, start, mid) maxRightIndex := m.getMaxIndex(prices, mid, end) centerProfit := prices[maxRightIndex] - prices[minLeftIndex] if centerProfit > leftResult.Profit && centerProfit > rightResult.Profit { return Result{centerProfit, minLeftIndex, maxRightIndex} } else if leftResult.Profit > centerProfit && rightResult.Profit > centerProfit { return leftResult } else { return rightResult } } func (m *Main) getMinIndex(prices []int, i, j int) int { minIndex := i for k := i + 1; k <= j; k++ { if prices[k] < prices[minIndex] { minIndex = k } } return minIndex } func (m *Main) getMaxIndex(prices []int, i, j int) int { maxIndex := i for k := i + 1; k <= j; k++ { if prices[k] > prices[maxIndex] { maxIndex = k } } return maxIndex } func main() { m := Main{} prices := []int{200, 500, 1000, 700, 30, 400, 900, 400, 50} start := 0 end := len(prices) - 1 result := m.maxProfit(prices, start, end) fmt.Printf("Maximum Profit (Divide & Conquer): %d, buy date index: %d, sell date index: %d ", result.Profit, result.BuyDateIndex, result.SellDateIndex) }
Maximum Profit(Divide & Conquer): 870, buy date index: 4, sell date index: 6