# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # 买卖股票的最佳时机 II
#
# * Slug: best-time-to-buy-and-sell-stock-ii
#
# * Date: 2018-06-22
#
# * Category: LeetCode
#
# * Tags: 数组, 算法
#
# * Author: timking
#
# * Summary: LeetCode - 探索 - 初级算法

# > [原文链接](https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/22/)

# 给定一个数组，它的第 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。
# ```

# ## 初步解答
#
# 初步看了题目之后，首先想到的是，寻找一个数组中的最小值，然后从该最小值下标的右数组再找最大值，两者相减就是收益，然后再将最大值下标的右数组重复操作，得到结果。

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        length = len(prices)
        if length <= 1:
            return 0
        min_price = min(prices)
        min_index = prices.index(min_price)
        left_prices = prices[min_index:]
        max_price = max(left_prices)
        max_index = left_prices.index(max_price) + min_index
        benefit = max_price - min_price
        if max_index < length:
            benefit += Solution().maxProfit(prices[max_index:])
        return benefit


a = [7,1,5,3,6,4]
Solution().maxProfit(a)


# 但是很可惜，这个结果和题目给出的结果不符。

# ## 第二次解答
#
# 再次审题之后发现，题目是要求求一个数组的最大收益。所以应当思考在何种方式下求出最大收益。
#
# 通过对题目数组，我们可以计算两天收益的相邻之差，得到一个新数组。这样就将问题转化，求该数组的累计和。

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        length = len(prices)
        if length <= 1:
            return 0
        benefits = []
        i = 1
        while i < length:
            benefit = prices[i] - prices[i-1]
            benefits.append( benefit if benefit > 0 else 0 )
            i+=1
        return sum(benefits)


# 提交到LeetCode上测试通过。emmm 算法是没什么问题了，但是执行时间是属于比较 low 的那一档。
#
# 接下来继续进行优化。

# ## 优化
#
# 优化思路：
#
# * 首先我们无需需要一个数组来存储邻接差，只需要创建一个数值来累加就好，这样就节省了一个函数调用（sum）和数组空间。
#
#
# * 其次，我们的思路是 邻接差 大于0 才累加，否则为0 。则我们可以判断 下一个值是否大于上一个值， 这样就节省一个三元表达式的判断。这里需要值得注意的是，我们需要用本地变量来保存两个值。
#
# 以下是他们之间的执行时间，可以看到，这次修改会给我们带来 25% 的性能提升。
#  
# **original**
# ```
# 2.06 µs ± 8.61 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
# ```
#
# **第一次修改**
# ```
# 1.54 µs ± 4.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
# ```
#
# 修改之后的代码如下:

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        length = len(prices)
        if length <= 1:
            return 0
        benefits = 0
        i = 1
        while i < length:
            second = prices[i]
            first = prices[i-1]
            if second - first > 0:
                benefits += second - first
            i+=1
        return benefits


# 提交上去之后，发现执行用例大约在60ms。再参考一下第一名 40ms 的答案。

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        profit = 0
        for i in range(1,len(prices)):
            if prices[i] > prices[i-1]:
                profit += prices[i]-prices[i-1]
        return profit


# %timeit Solution().maxProfit(a)

# 发现差距并没有想象中的大，至此解答就到这里。

# ## 变种问题
#
# 我们将这个问题变种一下，求在获得最大收益的同时，给出操作方案, 在不操作的时候为0，购买的时候为1，卖出的时候为2。
#
# 输出一个与 prices 等长的操作方案的 list。

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        length = len(prices)
        if length <= 1:
            return 0, [0] * length
        benefits = 0
        operations = {0: 0}
        i = 1
        while i < length:
            second = prices[i]
            first = prices[i-1]
            if second - first > 0:
                benefits += second - first
                operations[i-1] = 1
                operations[i] = 2
            else:
                operations[i] = 0
            i+=1
        return benefits, list(operations.values())


Solution().maxProfit(a)

StarcoderdataJupyterScriptsDedupFiltered