121.MaxProfit.cs

// 121. Best Time to Buy and Sell Stock

// You are given an array prices where prices[i] is the price of a given stock on the ith day.

// You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to
// sell that stock.

// Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
// Example 1:
// Input: prices = [7,1,5,3,6,4]
// Output: 5
// Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
// Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
// Example 2:
// Input: prices = [7,6,4,3,1]
// Output: 0
// Explanation: In this case, no transactions are done and the max profit = 0.

public class Solution {
    public 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] = Math.Max(max[i+1],prices[i]);
        }
        int profit = 0;
        for(int i=0;i<prices.Length-1;i++){
            if(prices[i]<max[i])
                profit = Math.Max(profit,max[i]-prices[i]);
        }
        return profit;
    }
}

public class Solution {
    //Intuition: We can keep track of the minimum price of the stock and 
    //the maximum profit we can achieve by selling the stock at the current price. 
    //We can then return the maximum profit.
    public int MaxProfit(int[] prices) {
        int profit = 0;
        int min = prices[0];
        for(int i = 1; i < prices.Length; i++){
            profit = Math.Max(profit, prices[i]-min);
            min = Math.Min(min, prices[i]);
        }
        return profit;
    }
}