Facebook Interview Question Java Developers
Country: United States
My O(nlongn) solution (Worse case O(n^2), best case O(n)):
My approach:
1. Find the max value in the array, we will buy all the stocks before the max and sell it at the max price.
2. Treat all elements after the max as a new array and repeat the steps until there is one or no element left.
public int maxProfit(int[] prices) {
return maxProfit(prices,0,prices.length);
}
public int maxProfit(int[] prices, int left, int right){
if(right-left <=1)return 0;
int[] cum = new int[prices.length];
int maxPoint = -1;
int maxPointIndex = -1;
for(int i=left;i<right;i++){
cum[i]+=prices[i];
if(i>left)cum[i]+=cum[i-1];
if(maxPoint<=prices[i]){
maxPoint = prices[i];
maxIndex = i;
}
}
return (maxIndex-left+1)*maxPoint-cum[maxIndex]+maxProfit(prices,maxIndex+1,right);
}
I took a stab at this tonight, to have a nice hour long puzzle to solve. My solution is brute-force, which I think is the only way to do this. I made some key assumptions, as the original question isn't very clear:
1. I can sell multiple times, but each time I sell *ALL* stock accumulated to date is sold. This means, I can "Buy, Buy, Buy, Sell <All>, Buy, Buy, Buy, Sell <All>". This makes things more complicated.
2. I can chose "no-op" for a given day, and neither buy nor sell.
3. All values are int.
using System;
namespace Warmups
{
public class StockWarmup
{
public enum Operation { Hold = 0, Buy = 1, Sell = 2 };
/// <summary>
/// Treat the Operation Array as a base-3 number and +1 to it.
/// If the number wraps (all entries 0), then return null marking the end of the sequence.
/// </summary>
/// <remarks>
/// Example of the Base-3 math:
/// [0] = 0 (Hold)
/// [1] = 0 (Hold)
/// [2] = 0 (Hold)
/// Now, +1
/// [0] = 1 (Buy)
/// [1] = 0 (Hold)
/// [2] = 0 (Hold)
/// Now, +1
/// [0] = 2 (Sell)
/// [1] = 0 (Hold)
/// [2] = 0 (Hold)
/// Now, +1
/// [0] = 0 (Hold) Note: Wrapped, need to carry
/// [1] = 1 (Buy)
/// [2] = 0 (Hold)
/// </remarks>
/// <param name="original"></param>
/// <returns></returns>
public static Operation[] GetNextOperationSequence(Operation[] original)
{
Operation[] newOperations = new Operation[original.Length];
bool carry = true; // Start with this, so the first available digit is bumped.
bool allHold = true; // if all values are 'hold', then we've wrapped and should stop processing
for (int i = 0; i < original.Length; i++)
{
if (carry)
{
if (original[i] == Operation.Hold)
{
newOperations[i] = Operation.Buy;
carry = false;
}
else if (original[i] == Operation.Buy)
{
newOperations[i] = Operation.Sell;
carry = false;
}
else if (original[i] == Operation.Sell)
{
newOperations[i] = Operation.Hold;
carry = true;
}
else
throw new InvalidOperationException("Unknown Operation Type");
}
else
{
newOperations[i] = original[i]; // no change. Copy over the field.
}
if (newOperations[i] != Operation.Hold)
allHold = false;
}
return (allHold == true) ? null : newOperations;
}
/// <summary>
/// Problem Statement: Say you have an array for which the ith element is
/// the price of a given stock on day i, you can buy
/// stock at any day, but can only buy once a day, but
/// if you sell the stock, you must sell all of them at once.
/// Maximize Profit
/// </summary>
/// <param name="stockPriceByDay"></param>
/// <returns>
/// First Tuple entry is the max profit found
/// Second item in the tuple is the hold/buy/sell pattern used
/// </returns>
public static (int, Operation[]) MaximizeProfit(int[] stockPriceByDay)
{
// The operation sequence (hold/buy/sell) to try. The empty array defaults
// to "hold" for all values, which is "0" in any base. (Note: Keep in mind
// this array is treated as a giant base-3 number, for calculation purposes).
Operation[] buySellHoldSequence = new Operation[stockPriceByDay.Length];
// The current max profit, and sequence of hold/buy/sell events used to
// calculate that sequence
int maxProfit = 0;
Operation[] currentMaxProfitSequence = (Operation[]) buySellHoldSequence.Clone();
bool keepGoing = true;
while(keepGoing)
{
int profit = CalculateProfit(stockPriceByDay, buySellHoldSequence);
if (profit > maxProfit)
{
maxProfit = profit;
currentMaxProfitSequence = (Operation[])buySellHoldSequence.Clone();
}
// Get the next periumation of the sequence
buySellHoldSequence = GetNextOperationSequence(buySellHoldSequence);
if (buySellHoldSequence == null)
keepGoing = false;
}
return (maxProfit, currentMaxProfitSequence);
}
public static int CalculateProfit(int[] stockPriceByDay, Operation[] operationOnEachDay)
{
int profit = 0;
int sharesOwned = 0;
for (int dayNumber = 0; dayNumber < stockPriceByDay.Length; dayNumber++)
{
switch (operationOnEachDay[dayNumber])
{
case Operation.Buy:
sharesOwned++;
profit -= stockPriceByDay[dayNumber];
break;
case Operation.Sell:
int currentPrice = stockPriceByDay[dayNumber];
profit += currentPrice * sharesOwned; // Note: Could be negative
sharesOwned = 0;
break;
case Operation.Hold: // No-op
break;
}
}
return profit;
}
}
}
As I love to do, I added many tests around this. My test sequences are:
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Warmups;
using static Warmups.StockWarmup;
namespace StockTests
{
[TestClass]
public class UnitTest1
{
[TestMethod]
public void ProfitCalculatorOneEntry()
{
int[] stocksByDay = { 100 };
Operation[] buySellOperations = { Operation.Buy };
int profit = StockWarmup.CalculateProfit(stocksByDay, buySellOperations);
Assert.AreEqual(profit, -100);
}
[TestMethod]
public void ProfitCalculatorTwoEntry()
{
int[] stocksByDay = { 100, 200 };
Operation[] buySellOperations = { Operation.Buy, Operation.Sell };
int profit = StockWarmup.CalculateProfit(stocksByDay, buySellOperations);
Assert.AreEqual(profit, 100);
}
[TestMethod]
public void ProfitCalculatorThreeEntry()
{
int[] stocksByDay = { 100, 200, 300 };
Operation[] buySellOperations = { Operation.Buy, Operation.Buy, Operation.Sell };
int profit = StockWarmup.CalculateProfit(stocksByDay, buySellOperations);
Assert.AreEqual(profit, 300);
}
[TestMethod]
public void GetNextSequenceOneEntryHold()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Hold });
Assert.IsTrue(result1.Length == 1);
Assert.IsTrue(result1[0] == Operation.Buy);
}
[TestMethod]
public void GetNextSequenceOneEntryBuy()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Buy });
Assert.IsTrue(result1.Length == 1);
Assert.IsTrue(result1[0] == Operation.Sell);
}
[TestMethod]
public void GetNextSequenceOneEntrySell()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell });
Assert.IsNull(result1);
}
[TestMethod]
public void GetNextSequenceTwoEntryHold()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Hold, Operation.Hold });
Assert.IsTrue(result1.Length == 2);
Assert.IsTrue(result1[0] == Operation.Buy);
Assert.IsTrue(result1[1] == Operation.Hold);
}
[TestMethod]
public void GetNextSequenceTwoEntryBuy()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Buy, Operation.Hold });
Assert.IsTrue(result1.Length == 2);
Assert.IsTrue(result1[0] == Operation.Sell);
Assert.IsTrue(result1[1] == Operation.Hold);
}
[TestMethod]
public void GetNextSequenceTwoEntrySell()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell, Operation.Hold });
Assert.IsTrue(result1.Length == 2);
Assert.IsTrue(result1[0] == Operation.Hold);
Assert.IsTrue(result1[1] == Operation.Buy);
}
[TestMethod]
public void GetNextSequenceThreeHoldBuyHold()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Hold, Operation.Buy, Operation.Hold });
Assert.IsTrue(result1.Length == 3);
Assert.IsTrue(result1[0] == Operation.Buy);
Assert.IsTrue(result1[1] == Operation.Buy);
Assert.IsTrue(result1[2] == Operation.Hold);
}
[TestMethod]
public void GetNextSequenceThreeSellSellHold()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell, Operation.Sell, Operation.Hold });
Assert.IsTrue(result1.Length == 3);
Assert.IsTrue(result1[0] == Operation.Hold);
Assert.IsTrue(result1[1] == Operation.Hold);
Assert.IsTrue(result1[2] == Operation.Buy);
}
[TestMethod]
public void GetNextSequenceThreeSellSellSell()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell, Operation.Sell, Operation.Sell });
Assert.IsNull(result1);
}
[TestMethod]
public void MaxProfitTwoEntries()
{
var profitResults = MaximizeProfit(new int[] { 100, 200 });
Assert.IsTrue(profitResults.Item1 == 100);
Assert.IsTrue(profitResults.Item2[0] == Operation.Buy);
Assert.IsTrue(profitResults.Item2[1] == Operation.Sell);
}
[TestMethod]
public void MaxProfitTwoEntriesLoseMoney()
{
var profitResults = MaximizeProfit(new int[] { 200, 100 });
Assert.IsTrue(profitResults.Item1 == 0);
Assert.IsTrue(profitResults.Item2[0] == Operation.Hold);
Assert.IsTrue(profitResults.Item2[1] == Operation.Hold);
}
[TestMethod]
public void MaxProfitThreeEntries()
{
var profitResults = MaximizeProfit(new int[] { 1, 3, 5});
Assert.IsTrue(profitResults.Item1 == 6);
Assert.IsTrue(profitResults.Item2[0] == Operation.Buy );
Assert.IsTrue(profitResults.Item2[1] == Operation.Buy);
Assert.IsTrue(profitResults.Item2[2] == Operation.Sell);
}
[TestMethod]
public void MaxProfitFourEntriesStaggeredSell()
{
var profitResults = MaximizeProfit(new int[] { 1, 3, 1, 2 });
Assert.IsTrue(profitResults.Item1 == 3);
Assert.IsTrue(profitResults.Item2[0] == Operation.Buy);
Assert.IsTrue(profitResults.Item2[1] == Operation.Sell);
Assert.IsTrue(profitResults.Item2[2] == Operation.Buy);
Assert.IsTrue(profitResults.Item2[3] == Operation.Sell);
}
}
}
I needed a puzzle this evening, so I took a stab at this. Some assumptions:
1. I can buy/sell/no-op on any given day.
2. I can sell multiple times, but must sell ALL stock at each time. So in a 4 day block, for example, I could: Buy / Sell / Buy / Sell
using System;
namespace Warmups
{
public class StockWarmup
{
public enum Operation { Hold = 0, Buy = 1, Sell = 2 };
/// <summary>
/// Treat the Operation Array as a base-3 number and +1 to it.
/// If the number wraps (all entries 0), then return null marking the end of the sequence.
/// </summary>
/// <remarks>
/// Example of the Base-3 math:
/// [0] = 0 (Hold)
/// [1] = 0 (Hold)
/// [2] = 0 (Hold)
/// Now, +1
/// [0] = 1 (Buy)
/// [1] = 0 (Hold)
/// [2] = 0 (Hold)
/// Now, +1
/// [0] = 2 (Sell)
/// [1] = 0 (Hold)
/// [2] = 0 (Hold)
/// Now, +1
/// [0] = 0 (Hold) Note: Wrapped, need to carry
/// [1] = 1 (Buy)
/// [2] = 0 (Hold)
/// </remarks>
/// <param name="original"></param>
/// <returns></returns>
public static Operation[] GetNextOperationSequence(Operation[] original)
{
Operation[] newOperations = new Operation[original.Length];
bool carry = true; // Start with this, so the first available digit is bumped.
bool allHold = true; // if all values are 'hold', then we've wrapped and should stop processing
for (int i = 0; i < original.Length; i++)
{
if (carry)
{
if (original[i] == Operation.Hold)
{
newOperations[i] = Operation.Buy;
carry = false;
}
else if (original[i] == Operation.Buy)
{
newOperations[i] = Operation.Sell;
carry = false;
}
else if (original[i] == Operation.Sell)
{
newOperations[i] = Operation.Hold;
carry = true;
}
else
throw new InvalidOperationException("Unknown Operation Type");
}
else
{
newOperations[i] = original[i]; // no change. Copy over the field.
}
if (newOperations[i] != Operation.Hold)
allHold = false;
}
return (allHold == true) ? null : newOperations;
}
/// <summary>
/// Problem Statement: Say you have an array for which the ith element is
/// the price of a given stock on day i, you can buy
/// stock at any day, but can only buy once a day, but
/// if you sell the stock, you must sell all of them at once.
/// Maximize Profit
/// </summary>
/// <param name="stockPriceByDay"></param>
/// <returns>
/// First Tuple entry is the max profit found
/// Second item in the tuple is the hold/buy/sell pattern used
/// </returns>
public static (int, Operation[]) MaximizeProfit(int[] stockPriceByDay)
{
// The operation sequence (hold/buy/sell) to try. The empty array defaults
// to "hold" for all values, which is "0" in any base. (Note: Keep in mind
// this array is treated as a giant base-3 number, for calculation purposes).
Operation[] buySellHoldSequence = new Operation[stockPriceByDay.Length];
// The current max profit, and sequence of hold/buy/sell events used to
// calculate that sequence
int maxProfit = 0;
Operation[] currentMaxProfitSequence = (Operation[]) buySellHoldSequence.Clone();
bool keepGoing = true;
while(keepGoing)
{
int profit = CalculateProfit(stockPriceByDay, buySellHoldSequence);
if (profit > maxProfit)
{
maxProfit = profit;
currentMaxProfitSequence = (Operation[])buySellHoldSequence.Clone();
}
// Get the next periumation of the sequence
buySellHoldSequence = GetNextOperationSequence(buySellHoldSequence);
if (buySellHoldSequence == null)
keepGoing = false;
}
return (maxProfit, currentMaxProfitSequence);
}
public static int CalculateProfit(int[] stockPriceByDay, Operation[] operationOnEachDay)
{
int profit = 0;
int sharesOwned = 0;
for (int dayNumber = 0; dayNumber < stockPriceByDay.Length; dayNumber++)
{
switch (operationOnEachDay[dayNumber])
{
case Operation.Buy:
sharesOwned++;
profit -= stockPriceByDay[dayNumber];
break;
case Operation.Sell:
int currentPrice = stockPriceByDay[dayNumber];
profit += currentPrice * sharesOwned; // Note: Could be negative
sharesOwned = 0;
break;
case Operation.Hold: // No-op
break;
}
}
return profit;
}
}
}
Tests are here:
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Warmups;
using static Warmups.StockWarmup;
namespace StockTests
{
[TestClass]
public class UnitTest1
{
[TestMethod]
public void ProfitCalculatorOneEntry()
{
int[] stocksByDay = { 100 };
Operation[] buySellOperations = { Operation.Buy };
int profit = StockWarmup.CalculateProfit(stocksByDay, buySellOperations);
Assert.AreEqual(profit, -100);
}
[TestMethod]
public void ProfitCalculatorTwoEntry()
{
int[] stocksByDay = { 100, 200 };
Operation[] buySellOperations = { Operation.Buy, Operation.Sell };
int profit = StockWarmup.CalculateProfit(stocksByDay, buySellOperations);
Assert.AreEqual(profit, 100);
}
[TestMethod]
public void ProfitCalculatorThreeEntry()
{
int[] stocksByDay = { 100, 200, 300 };
Operation[] buySellOperations = { Operation.Buy, Operation.Buy, Operation.Sell };
int profit = StockWarmup.CalculateProfit(stocksByDay, buySellOperations);
Assert.AreEqual(profit, 300);
}
[TestMethod]
public void GetNextSequenceOneEntryHold()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Hold });
Assert.IsTrue(result1.Length == 1);
Assert.IsTrue(result1[0] == Operation.Buy);
}
[TestMethod]
public void GetNextSequenceOneEntryBuy()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Buy });
Assert.IsTrue(result1.Length == 1);
Assert.IsTrue(result1[0] == Operation.Sell);
}
[TestMethod]
public void GetNextSequenceOneEntrySell()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell });
Assert.IsNull(result1);
}
[TestMethod]
public void GetNextSequenceTwoEntryHold()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Hold, Operation.Hold });
Assert.IsTrue(result1.Length == 2);
Assert.IsTrue(result1[0] == Operation.Buy);
Assert.IsTrue(result1[1] == Operation.Hold);
}
[TestMethod]
public void GetNextSequenceTwoEntryBuy()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Buy, Operation.Hold });
Assert.IsTrue(result1.Length == 2);
Assert.IsTrue(result1[0] == Operation.Sell);
Assert.IsTrue(result1[1] == Operation.Hold);
}
[TestMethod]
public void GetNextSequenceTwoEntrySell()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell, Operation.Hold });
Assert.IsTrue(result1.Length == 2);
Assert.IsTrue(result1[0] == Operation.Hold);
Assert.IsTrue(result1[1] == Operation.Buy);
}
[TestMethod]
public void GetNextSequenceThreeHoldBuyHold()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Hold, Operation.Buy, Operation.Hold });
Assert.IsTrue(result1.Length == 3);
Assert.IsTrue(result1[0] == Operation.Buy);
Assert.IsTrue(result1[1] == Operation.Buy);
Assert.IsTrue(result1[2] == Operation.Hold);
}
[TestMethod]
public void GetNextSequenceThreeSellSellHold()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell, Operation.Sell, Operation.Hold });
Assert.IsTrue(result1.Length == 3);
Assert.IsTrue(result1[0] == Operation.Hold);
Assert.IsTrue(result1[1] == Operation.Hold);
Assert.IsTrue(result1[2] == Operation.Buy);
}
[TestMethod]
public void GetNextSequenceThreeSellSellSell()
{
// Hold, Buy, Sell
var result1 = GetNextOperationSequence(new Operation[] { Operation.Sell, Operation.Sell, Operation.Sell });
Assert.IsNull(result1);
}
[TestMethod]
public void MaxProfitTwoEntries()
{
var profitResults = MaximizeProfit(new int[] { 100, 200 });
Assert.IsTrue(profitResults.Item1 == 100);
Assert.IsTrue(profitResults.Item2[0] == Operation.Buy);
Assert.IsTrue(profitResults.Item2[1] == Operation.Sell);
}
[TestMethod]
public void MaxProfitTwoEntriesLoseMoney()
{
var profitResults = MaximizeProfit(new int[] { 200, 100 });
Assert.IsTrue(profitResults.Item1 == 0);
Assert.IsTrue(profitResults.Item2[0] == Operation.Hold);
Assert.IsTrue(profitResults.Item2[1] == Operation.Hold);
}
[TestMethod]
public void MaxProfitThreeEntries()
{
var profitResults = MaximizeProfit(new int[] { 1, 3, 5});
Assert.IsTrue(profitResults.Item1 == 6);
Assert.IsTrue(profitResults.Item2[0] == Operation.Buy );
Assert.IsTrue(profitResults.Item2[1] == Operation.Buy);
Assert.IsTrue(profitResults.Item2[2] == Operation.Sell);
}
[TestMethod]
public void MaxProfitFourEntriesStaggeredSell()
{
var profitResults = MaximizeProfit(new int[] { 1, 3, 1, 2 });
Assert.IsTrue(profitResults.Item1 == 3);
Assert.IsTrue(profitResults.Item2[0] == Operation.Buy);
Assert.IsTrue(profitResults.Item2[1] == Operation.Sell);
Assert.IsTrue(profitResults.Item2[2] == Operation.Buy);
Assert.IsTrue(profitResults.Item2[3] == Operation.Sell);
}
}
}
You can put all the stock prices in a maxHeap with index as value. So the root is day when the price is max. Now, start to first day and keep buying until you hit the root idx. When you hit root idx, sell and also pop(). Then continue until you reach last day. That would do it in O(nlogn).
My solution in PHP (recursive function)
<?php
$stock = array(100, 180, 260, 310, 40, 535, 695);
getMaxProfit($stock,array(),0,$max,$op);
echo "Max Profit is : ".$max;
if(is_array($op)) echo " With the following actions : ".implode(",",$op);
function getMaxProfit($stock,$operations,$currentDay,&$maxReached,&$bestOperations){
if($currentDay == sizeof($stock)){
$profit = calculateProfit($stock,$operations);
if(!$maxReached) $maxReached=0;
if($profit <> null && $profit > $maxReached){
$maxReached=$profit;
$bestOperations=$operations;
}
return;
}
$operationsArray=array('Pass','Buy','Sell');
for($day=$currentDay;$day<sizeof($stock);$day++){
foreach($operationsArray as $operationValue){
$operations[$day]= $operationValue;
getMaxProfit($stock,$operations,$day+1,$maxReached,$bestOperations);
}
}
}
function calculateProfit($stock,$operations){
$profit=0;
$bought=0;
for($i=0;$i<sizeof($stock);$i++){
if(key_exists($i,$operations))
{
if($operations[$i] == 'Buy'){
$bought=1;
$profit-=$stock[$i];
}
elseif($operations[$i] == 'Sell'){
if($bought){
$profit+=$stock[$i];
$bought=0;
}
else return null;
}
}
}
return $profit;
}
?>
I don't believe I could write so much code in an interview. Here's my solution in 50 lines:
class Solution {
public static void main(String[] args) {
int[] array = {4,4,7,4,4,9,1,8};
Solution s = new Solution ();
int profit = s.maxProfit(array);
System.out.println("p="+profit);
}
int maxProfit(int[] prices) {
int peakDay = prices.length-1;
int peakPrice=prices[peakDay];
Transaction maxT = new Transaction();
for(int now=peakDay-1; now>=0 ; now--)
{
int currentPrice = prices[now];
if(currentPrice<peakPrice)
{
Transaction t = new Transaction();
for(int start = 0; start<peakDay; start++)
{
if (prices[start]<peakPrice)
{
t.profit += peakPrice-prices[start];
}
}
if(t.profit>maxT.profit)
{
maxT = t;
}
}
peakDay = now;
peakPrice = currentPrice;
}
return maxT.profit;
}
}
class Transaction {
int profit;
Transaction(){
profit = 0;
}
}
public static int maxProfit(int[] prices) {
int[] max = new int[prices.length];
max[prices.length - 1] = prices[prices.length - 1];
for (int i = prices.length - 2; i >= 0; i--)
max[i] = (prices[i] < max[i + 1] ? max[i + 1] : prices[i]);
int res = 0;
for (int i = 0; i < prices.length; i++)
if (max[i] > prices[i])
res += max[i] - prices[i];
return res;
}
If I say maxProfit(n) the max profile we can achieve in day n, and we hold 0 stock on day n.
and maxOneTimeProfit(i,j) is the max profit we can buy between i and j but sell only happened on day j.
then maxProfit(n+1) would be:
int max = 0;
for each i in 1..n:
max = math.max(max, maxProfit(i)+ maxOneTimeProfit(i..n+1))
maxProfit(n+1) = max;
static int maxOneTimeProfit(int[] prices, int i, int j)
{
int sum = 0;
for (int k=i; k<j; k++)
{
sum+= Math.max(prices[j] - prices[k], 0); // only buy at k if prices[j] > prices[k]
}
}
public static int maxProfit(int[] prices) {
int[] f = new int[prices.length];
f[0] = 0;
for (int j=1; j<prices.length; j++)
{
int max = 0;
for (int i=0; i<j; i++)
{
max = Math.max(f[k]+maxOneTimeProfit(prices, i, j), max);
}
}
return f[prices.length-1];
}
Simple and easy!
public int maxProfit(int[] prices)
{
Stack<Integer> stack = new Stack<Integer>();
int result =0;
for(int i=prices.length-1; i>=0; iii)
{
if(stack.isEmpty() || stack.peek() < prices[i])
{
stack.push(prices[i]);
}
}
for(int i =0; i<prices.length; i++)
{
if(prices[i] == stack.peek())
stack.pop();
else
{
result+= stack.peek() - prices[i];
}
}
return result;
}
import java.util.Arrays;
public class StockMaxProfit {
public static void main(String[] args){
int[] testcase1 = {1,2,10,9,100,6,20};
int actual = maxProfit(testcase1);
System.out.println("test " + Arrays.toString(testcase1) + " actual " + actual);
}
public static int maxProfit(int[] price){
int n = price.length;
int outlook[] = new int[n];
Arrays.fill(outlook, 0);
outlook[n-1] = price[n-1];
for (int i = n-2; i >= 0; i--){
if (price[i] > outlook[i+1]){
outlook[i] = price[i];
} else {
outlook[i] = outlook[i+1];
}
}
System.out.println(Arrays.toString(outlook));
int s = 0;
for (int i = 0; i < n; i++){
if (price[i] < outlook[i]){
s += (outlook[i] - price[i]);
}
}
return s;
}
}
- Ribix December 14, 2017public static int maxProfit(int[] prices) { int[] max = new int[prices.length]; max[prices.length - 1] = prices[prices.length - 1]; for (int i = prices.length - 2; i >= 0; i--) max[i] = (prices[i] < max[i + 1] ? max[i + 1] : prices[i]); int res = 0; for (int i = 0; i < prices.length; i++) if (max[i] > prices[i]) res += max[i] - prices[i]; return res; }