Maximum Profit, by Facebook

-
Daily Coding Problem:

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.

It seems very straightforward, and maybe I'm mistaken (although my solution seems to work fine), but here is the approach:

  •  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/BorisVasilenko/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!!!!


Comments

  1. TarasNovember 25, 2018 at 11:28 PM

    Great solution! This problem is also available on LeetCode - https://leetcode.com/problems/best-time-to-buy-and-sell-stock

    My 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

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more