题目地址 (opens new window)

  • 🙂 第一次练习 2020å¹´4月22日 这个题,很早以前自己就做过了,但是那个时候用的是一种笨办法,现在用动态规划的思路求解,感觉真的是精妙很多
  • 😄 第二次练习 2020å¹´4月22日 晚上再来练习这个题,第二次 算是孰能生巧吧。加油。。。。奥利给。。。

# 动态规划

解题代码

public int maxProfit(int[] prices) {
    int n = prices.length;
    int[][] dp = new int[n][2];

    // 第一天 没有持有为 0
    dp[0][0] = 0;

    // 第一天持有,说明买了股票
    dp[0][1] = -prices[0];

    for (int i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    return dp[n - 1][0];
}

# 以前自己的解法


public class maxProfit {
    public int maxProfit(int[] prices) {
        int total = 0;
        int begin = 0;
        int end = 0;
        boolean flag = false;
        for(int i = 0; i < prices.length - 1; i++){

            if(prices[i] < prices[i + 1] && !flag){
                begin = i;
                flag = true;
            }

            if(prices[i] > prices[i + 1] && flag){
                end = i;
                flag = false;
                total  = total + (prices[end] - prices[begin]);
            }
        }
        if(flag)
            total = total + (prices[prices.length - 1] - prices[begin]);

        return total;
    }

    public static void main(String[] args) {
        int[] arr = {7,1,5,3,6,4};
        System.out.println((new maxProfit()).maxProfit(arr));
    }
}

最后编辑时间: 7/12/2020, 9:51:48 PM