Be the first user to complete this post
|
Add to List |
552. Stock Single Sell Problem - Divide and Conquer
ObjectiveGiven 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.
Example:
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.
- The left half of the array. (Buy date index and sell date index both are in the left half of the array).
- The right half of the array. (Buy date index and sell date index both are in the right half of the array).
- 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