Leetcode刷题指南之121-Best Time to Buy and Sell Stock

  编程与算法之美报道  作者：东大ACM退役队伍编辑：Cookies题目分析给出股票每天的价格，先买入再卖出，问能赚的最大价钱是多少。解题思路这是一道典型的动态规划的题目。设dp为当前步骤能赚得的最大价钱，用min来维护当前最小值，则状态转移方程为dp = max（dp，prices [i] -min），即当前利润最大值为，上一步最大值和当前价格减去当前最小值中，较大的那一个。下面举个例子：输入：[7,1,5,3,6,4]这组数据，第三天是5，dp为4，mim为1，那么遍历到第四天时，新出现的值为3- 1 = 2，更新DP为DP（4）和2中的最大值，即为4。class Solution {public: int maxProfit(vectorint>& prices) { int len = prices.size(); if(len == 0) return 0; int dp = 0; int min = prices[0]; for(int i = 1; i dp = max(dp, prices[i]-min); if(prices[i] } return dp; }};粉 ………………………………