121.Best Time to Buy and Sell Stock

Posted on | In

Solution 1: accepted 3ms

DP.
Time: O(n)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i-1]) {
                max = Math.max(max, prices[i] - prices[i-1]);
                prices[i] = prices[i-1];
            }   
        }
        return max;
    }
}