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

题目

给你一个整数数组prices，其中prices[i]表示某支股票第i天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

返回 你能获得的 最大 利润 。

示例 1:

• 输入：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 。

示例 2:

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

示例 3:

• 输入：prices = [7,6,4,3,1]
• 输出：0
• 解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。

思路

这个的改动点时可以交易多次，怎么能保证利益最大？ 下面两种方式其实一样

方式一

只要第二天价格比第一天价格高就卖

class Solution {
    fun maxProfit(prices: IntArray): Int {
        var buyPirce = prices[0]
        var totalIncome = 0
        for (i in prices) {
            if (i > buyPirce) {
                totalIncome += (i - buyPirce)
                buyPirce = i
            } else if (i < buyPrice) {
                buyPirce = i
            }
        }
        return totalIncome
    }
}

方式二

• 记录当前可卖的最大收入及买入的价格
• 如果最新的价格低于买入的价格或者当前已经有收入了且当前的价格小于最大收入时的卖价(i - buyPrice < income)，这个时候需要卖了再买

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buyPrice = prices[0]
        income = 0
        totalIncome = 0
        for i in prices:

            if i < buyPrice or i - buyPrice < income: # 有更低的价格，或者说现在的价格比目前收益最大时可卖出的价格更低
                # 有更低的购买价格了，这个时候要判断当前有没有利润，有就卖，没有就使用该价格买
                if (income > 0):
                    totalIncome += income
                    income = 0
                buyPrice = i
            elif (i - buyPrice > income):
                income = i - buyPrice

        totalIncome += income
        return totalIncome

class Solution {
    fun maxProfit(prices: IntArray): Int {
        var count = 0
        var price = prices[0]

        for (i in prices) {
            if (i > price) {
                count += i - price
            }
            price = i
        }

        return count
    }
}

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!