My AC solution with O(n) time complexity and O(1) space complexity


  • -3
    M

    The approach is to buy the shares on day 0 itself and keep track of current minimum price. As soon as the current minimum changes, sell the previous stocks and buy again. Finally sell the stocks on the last day if you have any.

    public class Solution {
        public int maxProfit(int[] prices) {
           if(prices.length<=1)
           return 0;
           int  min=0;
           int profit =0;
           int i;
            for(i=1;i<prices.length;i++)
            {
                if(prices[i-1]>prices[i])
                {
                profit+=prices[i-1]-prices[min];
                min=i;
                }
            }
            if(min!=prices.length-1)
            profit+=prices[i-1]-prices[min];
            return profit;
        }
    }

  • 0
    M
    This post is deleted!

  • 0
    S
    This post is deleted!

Log in to reply
 

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