Wednesday 23 September 2015

Share price max profit recursive

Problem

You are given the prices of a given stock for some days. You were allowed to own at most one stock at any time and you must not hold any stock at the end of that period. You can do at most k transactions. Find out the maximum profit that you could have.

Solution

At any given day, if we own the stock we have two choices, either we can sell it or we can keep it. if we sell it, we have a subproblem of finding out the max profit with the rest of the days with one less transaction. If we don't sell it we have a subproblem of finding out the max profit with the rest of the days with the same number of transaction. We find out the maximum of this two scenarios. Similarly if we don't own the share at any given day we have two options, we can buy it or not.

Code

package dsalgo;

public class StockPriceMaxProfitRecursive {

 public static void main(String[] args) {
  int[] prices = { 400, 402, 435, 398, 378, 400, 432, 432, 402 };
  System.out.println(getMaxProfit(prices, 0, 7, false));
 }

 public static int getMaxProfit(int[] prices, int startDay,
   int maxTransaction, boolean hasStock) {
  if (maxTransaction == 0 || startDay == prices.length)
   return 0;
  if (hasStock) {
   return Math.max(
     getMaxProfit(prices, startDay + 1, maxTransaction, true),
     getMaxProfit(prices, startDay + 1, maxTransaction - 1,
       false) + prices[startDay]);
  } else {
   return Math.max(
     getMaxProfit(prices, startDay + 1, maxTransaction, false),
     +getMaxProfit(prices, startDay + 1, maxTransaction - 1,
       true) - prices[startDay]);
  }
 }

}

No comments:

Post a Comment