买卖股票的最佳时期2

[PisecesPeng]

买卖股票的最佳时期2

给定一个数组, 它的第 i 个元素是一支给定股票第 i 天的价格.
设计一个算法来计算你所能获取的最大利润.你可以尽可能地完成更多的交易(多次买卖一支股票).
注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票).
 

示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入, 在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 .
      随后, 在第 4 天（股票价格 = 3）的时候买入, 在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 .

示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入, 在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 .
     注意你不能在第 1 天和第 2 天接连购买股票, 之后再将它们卖出.
     因为这样属于同时参与了多笔交易, 你必须在再次购买前出售掉之前的股票.

示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0.

提示:
1 <= prices.length <= 3 * 10 ^ 4. 0 <= prices[i] <= 10 ^ 4.

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

[PisecesPeng]

解题思路

• 遍历数组, 判断前后收益, 累计.

代码

private static int func(int[] ints) {
    int length;
    if ((length = ints.length) <= 1) return 0;

    int result = 0;  // 收益
    boolean hasBuy = false;  // 是否已买入
    int buyPirce = 0;  // 买入金额
    for (int i = 1; i < length; i++) {
        if (ints[i - 1] > ints[i] && hasBuy) {  // 第i天的价格小于第i-1天的价格 且 是否早已买入
            // 将股票卖出, 重置为未买入状态
            result += ints[i - 1] - buyPirce;
            hasBuy = false;
            buyPirce = 0;
        } else if (ints[i - 1] < ints[i] && !hasBuy) {  // 第i天的价格大于第i-1天的价格
            // 买入股票, 更新买入状态
            hasBuy = true;
            buyPirce = ints[i - 1];
        }
        // ints[i-1] == ints[i], 不做任何操作.
    }
    // 若最后还为'买入'状态, 则将最后一天的股票卖出
    if (hasBuy) result += ints[length - 1] - buyPirce;
    return result;
}

[PisecesPeng]

LeetCode题解

解题思路

• 动态规划, 定义dp数组, 记录天数(下标)从0开始的状态,
• dp[i][0] 表示第i天交易完后手里没有股票的最大利润,
• dp[i][1] 表示第i天交易完后手里持有一支股票的最大利润.

代码

private static int func(int[] prices) {
    int n = prices.length;
    int[][] dp = new int[n][2];
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    for (int i = 1; i < n; ++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[n - 1][0];
}

[PisecesPeng]

LeetCode题解

解题思路

• 贪心算法, 计算每次交易的利润.

代码

private static int func(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;
}