wordpress文章图片显示错误,就业seo好还是sem,热门传奇网页游戏排行榜,做网站责任题目描述#xff1a; 给定一个数组#xff0c;它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易#xff08;即买入和卖出一支股票一次#xff09;#xff0c;设计一个算法来计算你所能获取的最大利润。 注意#xff1a;你不能在买入股票前卖出… 题目描述 给定一个数组它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易即买入和卖出一支股票一次设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。 示例 1:
输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。 注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。 示例 2:
输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 题目链接121:买卖股票的最佳时机
第一个思路使用双for循环然后就超时了。。
class Solution {
public:int maxProfit(vectorint prices) {int nprices.size();int ans0;for(int i0;in;i){for(int j0;ji;j){ans max(ans,prices[i]-prices[j]);}}if(ans0)ans0;return ans;}
};第二个思路dp[i]表示前i天能获取的最大价值 dp[i]由两种方式获取 1、计算前i-1天中买入的最小价格在第i天卖出的价格 2、计算前i-1天能获取的最大价值 两者取大值。 另外还需要注意 1、当输入为空数组时返回0(边界情况) 2、如果你新建了一个dp数组可以发现不需要直接用ans替换就行了因为我们只用到dp数组的两个状态。
class Solution {
public:int maxProfit(vectorint prices) {int nprices.size();if(n0) return 0;int ans0;int minnum prices[0];for(int i1;in;i){minnummin(minnum,prices[i]);ansmax(ans,prices[i]-minnum);}if(ans0)ans0;return ans;}
};
