题目链接

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

题目描述

prices[i]表示第i天的股票价格，怎么操作可以保证利润最大

输入输出样例

1
2
3
4
5
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

题目解释

计算i天买，i+1天卖的利润作为数组。

只算大于0的情况。

考虑折线图的情况

代码

个人实现

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int length = prices.size();
        int res = 0;
        for (int i = 1; i < length; i++) {
            res += max(0, prices[i] - prices[i - 1]);
        }
        return res;
    }
};

官方实现

作者：力扣官方题解
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/solutions/476791/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 贪心算法
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int length = prices.size();
        vector<vector<int>> dp(length, vector<int>(2, 0));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[length - 1][0];
    }
};