Question Link

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Question Description

Given an array of prices[], return maximum profix by choosing a single day to by stock, and different future day to sell stock.
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.

Simulation

Solution 1: Greedy

Greedy by maximize the profit in each single operation, and then maximize the global profit.

Implementation

Solution

public int maxProfit(int[] prices) {
    int profit = 0;
    int cost = Integer.MAX_VALUE;
    for (int price: prices) {
        profit = Math.max(profit, profit - cost);
        cost = Math.min(cost, price);
    }
    return profit;
}