C++ day49 买卖股票的最佳时机

2023-12-03 16:04

本文主要是介绍C++ day49 买卖股票的最佳时机,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目1:121 买卖股票的最佳时机

题目链接:买卖股票的最佳时机

对题目的理解

prices[i]表示一支股票在第i天的价格,只能在某一天买入这支股票,并在之后的某一天卖出该股票,从而获得最大利润,返回该最大值,若不能获取利润,则返回0

注意:股票只能买卖一次

暴力解法(超时)

class Solution {
public:int maxProfit(vector<int>& prices) {int result=0;for(int i=0;i<prices.size();i++){for(int j=i+1;j<prices.size();j++){result=max(result,prices[j]-prices[i]);}}return result;}
};
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

贪心解法

股票就买卖一次,那么贪心的想法很自然就是取最左最小值,取最右最大值,那么得到的差值就是最大利润

class Solution {
public:int maxProfit(vector<int>& prices) {int result=0;int low=INT_MAX;for(int i=0;i<prices.size();i++){low=min(low,prices[i]);result=max(result,prices[i]-low);}return result;}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

动态规划

动规五部曲

1)dp数组及下标i的含义(使用二维dp数组)

dp[i][0]表示第i天持有这支股票所拥有的最大现金,注意是持有,不一定是当天买入,可能是前天已经买入

dp[i][1]表示第i天不持有这支股票所拥有的最大现金,注意是持有,不一定是当天卖出,可能是前天已经卖出

最终求 dp[prices.size()][1]

本题中不持有股票状态所得金钱一定比持有股票状态得到的多

2)递推公式

dp[i][0] = dp[i-1][0]  一直持有该股票

dp[i][0] = -prices[i]  在第i天买入这支股票,减去股票的价格,因为只买卖一次,所以直接等于-princes[i]

dp[i][0]=max(dp[i-1][0], -prices[i])

dp[i][1] = dp[i-1][1] 一直不持有该股票

dp[i][1] = dp[i-1][0] + prices[i]  在第i天将这支股票卖了,那么前一天一定是持有这只股票,所以是二者相加

dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])

3)dp数组初始化

根据递推公式,dp[i]由dp[i-1]推出来,由前一个状态推出来

所以初始化,最前面的状态  第0天持有这支股票的最大现金(买入):dp[0][0]=-prices[0]   

 第1天不持有这支股票的状态(没有股票,不买入):dp[0][1]=0

4)遍历顺序

根据递推公式,后面状态依赖于前面的状态,所以从前往后进行遍历

for(int i=1;i<prices.size();i++){}

5)打印dp数组

代码

class Solution {
public:int maxProfit(vector<int>& prices) {//dp数组定义vector<vector<int>> dp(prices.size(),vector<int>(2));//初始化dp数组dp[0][0]=-prices[0];dp[0][1]=0;//递推for(int i=1;i<prices.size();i++){dp[i][0]=max(dp[i-1][0],-prices[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);}return dp[prices.size()-1][1];}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

题目2:122 买卖股票的最佳时机Ⅱ

题目链接:买卖股票的最佳时机Ⅱ

对题目的理解

prices[i]表示某支股票的第i天的价格,在每一天,都可以决定买入或者卖出股票,但是每天最多只能持有1支股票,可先购买,在同一天出售,返回获得的最大利润

可以多次买卖股票

贪心解法(利润分解)

假如第 0 天买入,第 3 天卖出,那么利润为:prices[3] - prices[0],相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

把利润分解为每天为单位的维度,只收集每天的正利润,注意至少要第2天才会有正利润

局部最优:收集每天的正利润,全局最优:求得最大利润

class Solution {
public:int maxProfit(vector<int>& prices) {int result = 0;for(int i=1;i<prices.size();i++){result += max(0,prices[i]-prices[i-1]);//收集正利润}return result;}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

动态规划

动规五部曲

1)dp数组及下标i的含义

dp[i][0]  :第i天持有股票的最大现金

dp[i][1]:第i天不持有股票的最大现金

2)递推公式

dp[i][0] = dp[i-1][0] :一直不持有股票

dp[i][0] = dp[i-1][1] - prices[i]  在第i天买入股票,因为题目中描述可以多次买卖股票,所以使用第i-1天不持有股票的最大现金减去股票的价格

dp[i][0]  = max(dp[i-1][0],dp[i-1][1]-prices[i])

dp[i][1] = dp[i-1][1] : 一直不持有股票

dp[i][1] = dp[i-1][0] + prices[i] 在第i天卖出股票,说明第i-1天一定持有股票

dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])

3)dp数组初始化

根据递推公式,后面的状态由前面的状态推导出来的,所以初始化dp[0][0]和dp[0][1]

dp[0][0]=-prices[0]

dp[0][1]=0

4)遍历顺序

根据递推公式,后面状态由前面状态推导,所以从前向后遍历

for(i=1;i<prices.size();i++)  注意这里是从1开始遍历的,因为i的状态,取决于i-1的状态

5)打印dp数组

代码

class Solution {
public:int maxProfit(vector<int>& prices) {//定义dp数组vector<vector<int>> dp(prices.size(),vector<int>(2,0));//初始化dp数组dp[0][0] = -prices[0];dp[0][1] = 0;for(int i=1;i<prices.size();i++){dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]);}return dp[prices.size()-1][1];}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

这篇关于C++ day49 买卖股票的最佳时机的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/450014

相关文章

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量,在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员,因为执行构造函数时,类对象已经创建完成,只有类对象创建完成才能调用成员函数,构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化,该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面,主要用于给

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(