题解 | #买卖股票的最好时机(一)#

package com.hhdd.dp;

/**
 * 不会 o(n)的解法
 *
 * @Author huanghedidi
 * @Date 2022/8/7 13:09
 */
public class 买卖股票的最好时机1 {

    public static void main(String[] args) {
        int[] arr = {2, 4, 7, 11};
        int res = maxProfit2(arr);
        System.out.println("res = " + res);


    }

    /**
     * 暴力做
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        // write code here
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                res = Math.max(res, prices[j] - prices[i]);
            }
        }

        return res < 0 ? 0 : res;
    }

    /**
     * 贪心的思想做
     * 维护个最小的买价，最大利润必然是当天价格 - 最小买价得到
     *
     * @param prices
     * @return
     */
    public static int maxProfit2(int[] prices) {
        int minBuy = prices[0];
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i < prices.length; i++) {
            ans = Math.max(ans, prices[i] - minBuy);
            minBuy = Math.min(minBuy, prices[i]);
        }
        return ans < 0 ? 0 : ans;
    }

}