wordpress cdn插件,seo研究中心倒闭,seo都用在哪些网站,烟台网站制作厂家电话文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a;股票要想盈利#xff0c;必须低买高卖。在第N天买入#xff0c;然后在第M天卖出#xff0c;所获的利… 文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析股票要想盈利必须低买高卖。在第N天买入然后在第M天卖出所获的利润是price[M]-price[N]而这个利润公式可以分解成 p r i c e [ M ] − p r i c e [ N ] ( p r i c e [ M ] − p r i c e [ M − 1 ] ) ( p r i c e [ M − 1 ] − p r i c e [ M − 2 ] ) . . . ( p r i c e [ N 2 ] − p r i c e [ N 1 ] ) ( p r i c e [ N 1 ] − p r i c e [ N ] ) \begin{align*} price[M]-price[N](price[M]-price[M-1])(price[M-1]-price[M-2])... \\ (price[N2]-price[N1])(price[N1]-price[N]) \end{align*} price[M]−price[N](price[M]−price[M−1])(price[M−1]−price[M−2])...(price[N2]−price[N1])(price[N1]−price[N]) 即N买M卖的利润可以由M和N天中间的股票价格的差值得到因此我们去计算price数组后一个元素与前一个元素的差值。取差值数组的和就是最终所得最大利润。 程序如下
class Solution {
public:int maxProfit(vectorint prices) {int result 0;for (int i 0; i prices.size() - 1; i) {result max(prices[i 1] - prices[i], 0);}return result;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( 1 ) O(1) O(1)。
三、完整代码
# include iostream
# include vector
# include algorithm
using namespace std;class Solution {
public:int maxProfit(vectorint prices) {int result 0;for (int i 0; i prices.size() - 1; i) {result max(prices[i 1] - prices[i], 0);}return result;}
};int main() {vectorint prices { 7,1,5,3,6,4 };Solution s1;int result s1.maxProfit(prices);cout result endl;system(pause);return 0;
}end
