【算法与数据结构】122、LeetCode买卖股票的最佳时机 II

2023-12-18 11:22:34

所有的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[N+2]-price[N+1])+(price[N+1]-price[N]) \end{align*} price[M]?price[N]?=(price[M]?price[M?1])+(price[M?1]?price[M?2])+...+(price[N+2]?price[N+1])+(price[N+1]?price[N])?
??即N买M卖的利润可以由M和N天中间的股票价格的差值得到,因此我们去计算price数组后一个元素与前一个元素的差值。取差值数组的和就是最终所得最大利润。
??程序如下

class Solution {
public:
	int maxProfit(vector<int>& 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(vector<int>& 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() {
	vector<int> prices = { 7,1,5,3,6,4 };
	Solution s1;
	int result = s1.maxProfit(prices);
	cout << result << endl;
	system("pause");
	return 0;
}

end

文章来源:https://blog.csdn.net/qq_45765437/article/details/135054836
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。