O(n) Time + O(n) Space in C#


  • 0
    K
    public class Solution 
    {
            public int MaxProfit(int[] prices)
            {
                if (prices.Length == 0 || prices.Length == 1) return 0;
    
                int previous = 0;            
                ArrayList profitList = new ArrayList();
    
                for (int i = prices.Length - 1; i > 0; i--)
                {
                    if (previous >= 0)
                        previous += (prices[i] - prices[i - 1]);
                    else
                        previous = (prices[i] - prices[i - 1]);
    
                    profitList.Add(previous);
                }
    
                return getBiggestNumber(profitList);
            }
            int getBiggestNumber(ArrayList a)
            {      
                a.Sort();
                if ((int)a.GetRange(a.Count - 1, 1).ToArray().GetValue(0) < 0)
                    return 0;
                else
                    return ((int)a.GetRange(a.Count - 1, 1).ToArray().GetValue(0));
            }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.