Maximum Profit, by Facebook
Daily Coding Problem:
It seems very straightforward, and maybe I'm mistaken (although my solution seems to work fine), but here is the approach:
GitHub: https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem10312018.cs
Code:
Happy Halloween!!!!
This problem was asked by Facebook.
Given a array of numbers representing the stock prices of a company in chronological order, write a function that calculates the maximum profit you could have made from buying and selling that stock once. You must buy before you can sell it.
For example, given [9, 11, 8, 5, 7, 10], you should return 5, since you could buy the stock at 5 dollars and sell it at 10 dollars.
- Keep track of min thus far
- Check whether the current profit is larger than max
- Make sure to return 0 if the max profit is negative (better to not buy/sell anything!)
- Linear time, constant space
GitHub: https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem10312018.cs
Code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace DailyCodingProblem
{
class DailyCodingProblem10312018
{
public int MaxProfit(int[] prices)
{
if (prices == null) return 0;
int minSoFar = Int32.MaxValue;
int maxProfit = Int32.MinValue;
for (int i = 0; i < prices.Length; i++)
{
int currentProfit = prices[i] - minSoFar;
if (currentProfit > maxProfit) maxProfit = currentProfit;
minSoFar = Math.Min(minSoFar, prices[i]);
}
return maxProfit > 0 ? maxProfit : 0;
}
}
}
Happy Halloween!!!!
Great solution! This problem is also available on LeetCode - https://leetcode.com/problems/best-time-to-buy-and-sell-stock
ReplyDeleteMy solution in C++ uses a few small improvements to make it shorter:
class Solution {
public:
int maxProfit(const vector& prices) {
int max_profit = 0;
int min_price = numeric_limits::max();
for (int price : prices) {
max_profit = max(max_profit, price - min_price);
min_price = min(min_price, price);
}
return max_profit;
}
};
You can technically use all of the shortcuts used above in C# - use foreach instead of a for loop for iterating over prices, use max to avoid explicit if statement in a loop body and initialize maxProfit to 0 in order to simplify return maxProfit > 0 ? maxProfit : 0 to just return maxProfit
Cheers,
Taras