Stock Single Sell Problem – O(n) Solution

Objec­tive:  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.

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

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.

Time Complexity: O(n^2)

Code:

public class StockSingleSellBruteForce {
public static void maxProfit(int [] prices){
int profit = 1;
int buyDateIndex = prices[0];
int sellDateIndex = prices[0];
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]>profit)) {
profit = prices[j] prices[i];
buyDateIndex = i;
sellDateIndex = j;
}
}
}
System.out.println("Maximum Profit: " + profit + ", buy date index: " + buyDateIndex +
", sell date index: " + sellDateIndex);
}
public static void main(String[] args) {
int [] prices = { 200, 500, 1000, 700, 30, 400, 900, 400, 50};
maxProfit(prices);
}
}

Approach 2: Divide and Conquer

1.     The approach is quite similar to “Maximum Subarray Problem – Divide and Conquer

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.

  1. Now we can conclude the final result will be in one of the three possibilities.
    1. Left half of the array. (Buy date index and sell date index both are in left half of the array).
    2. Right half of the array. (Buy date index and sell date index both are in right half of the array).
    3. 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).
  2. Solve the all three and return the maximum among them.
  3. Left half and right half of the array will be solved recursively.
  4. Maintain an object to keep track of profit and date indexes.

Time Complexity: O(nlogn)

Code:

public class StockSingleSellDandC {
public Result maxProfit(int [] prices, int start, int end){
if(start>=end){
return new Result(0,0,0);
}
int mid = start + (endstart)/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) {
StockSingleSellDandC m = new StockSingleSellDandC();
int [] prices = { 200, 500, 1000, 700, 30, 400, 900, 400, 50};
int start = 0;
int end = prices.length1;
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;
}
}


Approach 3: Dynamic Programming

  1. Iterate through last date index to start date index.
  2. Keep track of the maximum stock price seen during iteration, say it is max_sell_price and current_profit.
  3. For any i-th day, there are only two possibilities –
    1. Either price on the i-th day is greater than max_sell_price, in that case update the max_sell_price with that price.
    2. 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.
  4. After the iteration, return current_profit.
  5. See the code for more understanding.

Time Complexity: O(n)

Code:

public class StockSingleSellDP {
public static void maxProfit(int[] prices) {
int period = prices.length;
int buyDateIndex = 0;
int tempIndex = 0;
int sellDateIndex = 0;
int current_profit = 0;
int max_sell_price = prices[period 1]; //assign the last element
for (int i = period 2; i > 0; i) {
if (max_sell_price < prices[i]) {
max_sell_price = prices[i];
tempIndex = i;
} else if (max_sell_price > prices[i]) {
if (current_profit < max_sell_price prices[i]) {
current_profit = max_sell_price prices[i];
buyDateIndex = i;
sellDateIndex = tempIndex;
}
}
}
System.out.println("Maximum Profit(DP): " + current_profit + ", buy date index: " + buyDateIndex +
", sell date index: " + sellDateIndex);
}
public static void main(String[] args) {
int[] prices = {200, 500, 1000, 700, 30, 400, 900, 400, 50};
maxProfit(prices);
}
}


Output:

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

1 thought on “Stock Single Sell Problem – O(n) Solution”

  1. private static void findMaxProfit(int[] prices) {

    int min = 0;
    int profit = 0;
    int buyDateIndex = 0;
    int sellDateIndex = 0;

    for(int i = 0; i < prices.length; i++) {

    if (prices[i] profit) {
    profit = currentProfit;
    buyDateIndex = min;
    sellDateIndex = i;
    }
    }

    System.out.println(“Maximum profit is ” + profit + ” Buy Date Index is ”
    + buyDateIndex + ” Sell Date Index ” + sellDateIndex);
    }

    Reply

Leave a Reply to lipsa patel Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.