Share my simple dp java solution, O(n) time and O(1) space


  • 0
    H
    public class Solution {
        public int maxProfit(int[] prices) {
            if (prices.length < 2) {
                return 0;
            }
            int s = 0, e = prices.length - 1;
            int min = prices[0], profit = 0;
            while (s < e) {
                int next = s + 1;
                if (prices[s] < prices[next]) {
                    profit = Math.max(profit, prices[next] - prices[s]);
                    profit = Math.max(profit, prices[next] - min);
                    min = Math.min(min, prices[s]);
                }
                s++;
            }
            return profit;
        }
    }

Log in to reply
 

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