LeetCode 初级算法 maxProfit

灰太狼 2022-05-17 08:17 130阅读 0赞

# 题目 #

给定一个数组，它的第 *i* 个元素是一支给定股票第 *i* 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

**示例 1:**

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

# 思路 #

由于可以进行**多次买卖**，而不是只能一次，所以不要将本题误解为 **Maximum-Subarray Problem** （最大子串和问题）

只需要保证每次买卖都能盈利，也就是保证卖出价格 > 买入价格，就能达到最大利润。

巧妙地用一个数组Change来记载价格的变动（当天价格与前一天价格的差值）：

**Change\[ i \] = Price\[ i \] - Price \[ i -1 \]**

把非负项求和，即为最大利润。

# 代码 #

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

发表评论取消回复

表情：

评论列表（有 0 条评论，130人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode（初级算法）数组篇---旋转数组

题目将包含 n 个元素的数组向右旋转 k 步。例如，如果 n = 7 , k = 3，给定数组 `[1,2,3,4,5,6,7]` ，向右旋转后的结果为 `[5,6

绝地灬酷狼/ 2022年05月26日 07:10/ 0 赞/ 155 阅读

相关 LeetCode（初级算法）数组篇---存在重复

题目给定一个整数数组，判断是否存在重复元素。如果任何值在数组中出现至少两次，函数应该返回 true。如果每个元素都不相同，则返回 false。解析在这道

男娘i/ 2022年05月26日 03:43/ 0 赞/ 167 阅读

相关 LeetCode（初级算法）动态规划篇---爬楼梯

题目假设你正在爬楼梯。需要 n 步你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例

末蓝、/ 2022年05月25日 13:44/ 0 赞/ 157 阅读

相关 LeetCode 初级算法 maxProfit

题目给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注

灰太狼/ 2022年05月17日 08:17/ 0 赞/ 131 阅读

相关 LeetCode 初级算法 RemoveDuplicates

问题：给定一个排序数组，你需要在[原地][Link 1]删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在[原地]

﹏ヽ暗。殇╰゛Y/ 2022年05月17日 08:10/ 0 赞/ 128 阅读

相关 LeetCode 初级算法加一

思路：将列表转换成数字，数字转换成字符串，再生成一个列表。代码： class Solution(object): def plusOne(self

朱雀/ 2022年05月17日 07:59/ 0 赞/ 135 阅读

相关 LeetCode（初级算法）旋转数组

思路（1）数组切片 i = k % len(nums) nums\[:\] = nums\[-i:\]+nums\

布满荆棘的人生/ 2022年05月17日 07:51/ 0 赞/ 156 阅读

相关 Leetcode初级算法验证回文字符串（Python）

问题描述：给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。 ![70][] 算

快来打我*/ 2022年05月10日 13:42/ 0 赞/ 144 阅读

相关 Leetcode初级算法打家劫舍（动态规划）（Python实现）

问题描述： ![70][] 算法思想：该问题的内在逻辑结构依然是动态规划里的经典结构。最关键的是推出状态转移方程，当前规模的对应解法由更低规模的解法，仿佛拾级而上，站在

左手的ㄟ右手/ 2022年05月05日 23:54/ 0 赞/ 163 阅读

相关 LeetCode初级算法-数组-买股票最佳时机

因为能预测到明天发生什么，所以，如果把走势图画出来（随便画，要么往上要么往下的折线图）就好理解了，不管怎么样，只要往上走的的部分都是你利润，往下走的不用管。因为有上一题的缘故，

淡淡的烟草味﹌/ 2022年02月24日 12:10/ 0 赞/ 155 阅读