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

package org.example.test;

public class DynamicTest {
    /**
     * dp[] 定义为以 i 为结尾的最大收益。
     * 算法公式为：
     * if (dp[i - 1] < 0) {
     *     dp[i] = prices[i] - prices[i - 1];
     * } else {
     *     dp[i] = prices[i] - (prices[i - 1] - dp[i - 1]);
     * }
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        // write code here
        int length = prices.length;
        if (length == 1) {
            return 0;
        }
        int[] dp = new int[length];
        dp[0] = 0;
        dp[1] = prices[1] - prices[0];
        int max = dp[1];
        for (int i = 2; i < length; i++) {
            if (dp[i - 1] < 0) {
                dp[i] = prices[i] - prices[i - 1];
            } else {
                dp[i] = prices[i] - (prices[i - 1] - dp[i - 1]);
            }
            max = Math.max(max, dp[i]);
        }
        return Math.max(max, 0);
    }
}