122. 买卖股票的最佳时机 II

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

• 自己的解答

public int maxProfit(int[] prices) {
    int ans = 0;
    int i=0;
    int j;
    while(i<prices.length){

        for(j=i+1;j<prices.length;j++){
            if(prices[j]<=prices[j-1]){
                if(j-1>i){
                    ans += prices[j-1]-prices[i];
                }
                break;
            }
            if(j==prices.length-1){
                ans += prices[j]-prices[i];
                break;
            }

        }
        i=j;
    }
    return ans;
}

• 动态规划

image.png

public int maxProfit(int[] prices) {
    int[][] dp = new int[prices.length][2];
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    for(int i=1;i<prices.length;i++){
        dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
        dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
    }
    return dp[prices.length-1][0];
}

• 贪心

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