首页 > 编程语言 >C++练习:股票买卖的最佳时机(1~4)

C++练习:股票买卖的最佳时机(1~4)

时间:2024-10-30 11:18:53浏览次数:3  
标签:股票买卖 vector int max C++ 最佳时机 ans prices dp

121. 买卖股票的最佳时机

简介

这是一道简单题,思路是找卖出那一天前的最低价格,然后记录卖出后的最大利润。按照动态规划的思路解题,我们需要找到原问题和子问题的转移关系。

分析:n天内的最大利润,一定是1~n内某一天卖出股票的最大利润。我们知道要使我们手中的股票得到最大利润,就要在之前的最低价格购买。所以我们只要建立一个最低价格数组minimon,记录第i天前的最低价格,我们就可以得到第i天卖出股票的最大利润prices[i] - minimon[i]。

而如何维护minimon数组?显然minimon[i]肯定是minimon[i-1](之前的最低价)和prices[i](第i天的价格)二者之一。故我们得到状态转移方程minimon[i] = min(minimon[i-1],prices[i]);

因为维护最低价格数组和计算当天最大利润和记录最大利润可以一起进行,所以只需要一次遍历就能的到答案。

代码

int maxProfit(vector<int>& prices) {
        int ans = 0, n = prices.size();
        vector<int> dp(n, 0);
        dp[0] = prices[0];
        for(int i = 1; i < n; ++ i){
            dp[i] = min(dp[i-1], prices[i]);
            int profit = prices[i] - dp[i];
            ans = max(ans, profit);
        }
        return ans;
    }

优化

观察到在计算profit时只会用到最新的一个最低价,故可以用一个数来记录最新的最低价,而免去使用数组。且更改最低价和记录最大利润不会同时进行(同一天买卖的利润为0)。

代码

int maxProfit(vector<int>& prices) {
        int ans = 0, low = prices[0];
        for(int i = 1; i < prices.size(); ++ i){
            if(prices[i] < low){
                low = prices[i];
            }
            else{
                ans = max(ans, prices[i] - low);
            }
        }
        return ans;
    }

评价

比起动态规划,我觉得这题更像是贪心。只要找到最大的正向落差就可以了。

122. 买卖股票的最佳时机 II

简介

这题是非常简单的贪心问题。我们只需要记录每一天的纯利润的累计,就可以得到答案了。即只要今天的价格比前一天高我们就把这个高出的部分加入答案。相当于我们每天都买入股票,然后到第二天选择高价卖出或原价卖出,稳赚不赔啊。

代码

int maxProfit(vector<int>& prices) {
        int ans = 0, price = prices[0];
        for(int i = 0; i < prices.size(); ++ i){
            if(prices[i] > price){
                ans += prices[i] - price;
            }
            price = prices[i];
        }
        return ans;
    }

123. 买卖股票的最佳时机 III

方法一

这一题与第一题没有本质的区别,只是多了一次交易次数。相信在有了第一题的基础上,我们能很快得到一种解法。这里先给出代码,相信大家一眼就能看出。

int maxProfit(vector<int>& prices) {
        int ans = 0;
        int n = prices.size();
        vector<int> dp(n, 0);
        int lowPri = prices[0];
        for(int i = 1; i < n; ++ i){
            if(prices[i] < lowPri) lowPri = prices[i];
            else{
                dp[i] = prices[i] - lowPri;
                ans = max(ans, dp[i]);
            }
        } // 0~i的最大利润
        if(n < 4) return ans;
        int highPri = prices[n-1], maxPro = 0;
        for(int i = n-2; i > 0;  -- i){
            if(prices[i] > highPri){
                highPri = prices[i];
            }
            else{
                dp[i] = highPri - prices[i];
                maxPro = max(maxPro, dp[i]);
            }
            ans = max(ans, dp[i-1]+maxPro);
        } // i~n的最大利润
        return ans;
    }

思路很简单,我们只要把数组分成两部分分别计算每部分的最大利润,不同的划分方法有不同的总利润,通过比较每一种划分的总利润我们就可以得到答案。代码里做了一些优化,在有了dp[i]前部分的最大利润之后,我们只需要知道后半部分i+1~n的最大利润就能得到总利润了。通过反向计算,我们可以用和第一题同样的方法计算后半部分i+1~n的最大利润。

方法二

当然这个求序列划分的题目我们可以用动态规划来解决。让我们先来确定一个原始问题,我们把进行两次交易后账户的金额作为我们的原问题(只进行一次交易或不进行交易的情况可以视为在同一天买进卖出,这样利润为0不会对结果产生影响),我们要求原问题的最大值。现在我们要找状态转移关系。第二次交易后的总利润,应该是第一次交易利润加上的二次交易的利润。而一次买卖有分成低价买入,高价卖出两部分。所以我们的账户的金额是这样变化的:

amount0(初始资金,设为0)--->amount0 - prices[i](第一次买入,记为amount1) --->amount1+prices[j](第一次卖出,记为amount2)--->amount2-prices[k](第二次买入,记为amount3)--->amount3+prices[l](最终利润,记为amount4)

因为amount0=0,可以忽略。所以我们可以由四个状态推出原问题。而每个状态的我们可以找出它的子问题。比如对于amount1[i]它是第一次买入时的花费price的相反数,通过第一题我们知道price代表第i天前的最低价格。所以amount1[i] = max(amount1[i-1], prices[i])。同第一题最大利润amount2[i] = max(amount2[i-1], prices[i] + amount1[i]),后面的一项指把手中的股票卖出后的账户金额。

而对应amount3它指的是第一次交易完成后再购买股票后的账户金额。当j==k时,即同一天卖出买入,没有利润,相当于只进行了一次交易。amount3[i] = max(amount3[i-1], amount2[i] - prices[i])。

相信看到这里我们可以很容易的到amount4[i] = max(amount4[i-1], amount3[i] - prices[i])。

代码:

int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(4, 0));
        dp[0][0] = -prices[0], dp[0][2] = -prices[0];

        for(int i = 1; i < n; ++i){
            dp[i][0] = max(dp[i-1][0], -prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i][0] + prices[i]);
            dp[i][2] = max(dp[i-1][2], dp[i][1] - prices[i]);
            dp[i][3] = max(dp[i-1][3], dp[i][2] + prices[i]);
        }

        return dp[n-1][3];
    }

优化

观察到数组的每一列之和前一列和当前列有关,可以用滚动数组优化,做法也和第一题类似

int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(2, vector<int>(2, 0));
        dp[0][0] = -prices[0], dp[1][0] = -prices[0];

        for(int i = 1; i < n; ++i){
            dp[0][0] = max(dp[0][0], -prices[i]);
            dp[0][1] = max(dp[0][1], dp[0][0] + prices[i]);
            dp[1][0] = max(dp[1][0], dp[0][1] - prices[i]);
            dp[1][1] = max(dp[1][1], dp[1][0] + prices[i]);
        }

        return dp[1][1];
    }

记住这个格式,下一题会用到

188. 买卖股票的最佳时机 IV

孰能生巧,相信做到这里。大家对于这类题目不说一眼秒杀,也能信手捏来。

这里就直接给代码了

int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>> fund(k, vector<int>(2, 0)); // 账户资金
        for(int i = 0; i < k; ++ i) // 第笔交易买入后的资金
            fund[i][0] = -prices[0];
        for(int i = 1; i < prices.size(); ++ i){
            fund[0][0] = max(fund[0][0], -prices[i]);
            fund[0][1] = max(fund[0][1], prices[i] + fund[0][0]);
            for(int j = 1; j < k; ++ j){
                // 第i笔交易买入后的资金是第i-1笔交易卖出后的资金减去买股票的钱
                fund[j][0] = max(fund[j][0], fund[j-1][1] - prices[i]);
                // 第i笔交易卖出后的资金,即前i笔交易的最大总利润
                fund[j][1] = max(fund[j][1], prices[i] + fund[j][0]);
            }   
        }
        return fund[k-1][1];  // 返回最大总利润
    }

总结

对于这类的动态规划题目,我们只要找到子问题和原问题之间的状态转移关系,就已经解决80%的问题了。当然这也是题目的难点。还有一个要注意的地方就是,我们要求的问题可能不是可以直接动态规划的,这时我们就要找到一个与题目问题相关又能分解成子问题的原问题。就像第三题,我们把求不超过两次交易的最大利润,转化为求两次交易后的最大账户资金。就像把求最长子序列,转化为求包含第i个元素的最长序列。总之我们要把握住动态规划的五步,1.找到原问题,2.分解子问题,3.确定初始条件,4.状态转移,5.判断边界条件。

因为动态规划需要存储子问题的状态,所以也经常会用到状态压缩。就像本文用到的滚动数组。

标签:股票买卖,vector,int,max,C++,最佳时机,ans,prices,dp
From: https://blog.csdn.net/weixin_64911856/article/details/143333196

相关文章

  • list(c++)
    list介绍list是STL容器中的容器,且元素在容器中的位置是分散的并与大小无关。list的底层是双向链表,其优势是在任意位置插入和删除元素的时间复杂度为O(1),但无法通过“下标[]”直接访问元素,需要通过从头(尾)遍历元素找到元素,多用于需要大量数据的插入和删除,且对数据的随机访问比......
  • 基于 C++ 的 UG/NX 二次开发环境配置
    基于C++的UG/NX二次开发环境配置参考教程:UG/NX二次开发环境配置方法(nx1980+vs2019)-CSDN博客NX二次开发VS环境搭建-怡宁塑胶模具设计-博客园(cnblogs.com)NX/UG二次开发环境配置方法—史上最详细版(以NX11.0和VisualStudio2017为例)_nx二次开发-CSDN博客在Windows......
  • C++:日期类的实现
      目录一.日期类1.类的构造函数和拷贝构造2.日期的比较3.日期加减一个天数1.日期加天数2.日期减天数4.日期的++与--1.日期的++2.日期的--5.日期减日期6.日期的输入和输出二.整体代码1.Date.h2.Date.cpp      在前面几节的内容中,我们学习了类的基本......
  • 【C/C++】5.并发控制
    并发控制(ConcurrencyControl)是指在多线程或多进程环境中,确保多个操作在共享资源上的访问不会发生冲突或产生不一致的情况。并发控制的核心目标是在允许并发操作的同时,保证系统的正确性、数据的一致性和完整性。在并发环境下,不同的线程或进程可能会同时访问共享资源(例如变量、文......
  • 每日OJ题_牛客_AB20走迷宫_BFS_C++_Java
    目录牛客_AB20走迷宫_BFS题目解析C++代码Java代码牛客_AB20走迷宫_BFS走迷宫_牛客题霸_牛客网(nowcoder.com)描述:        给定一个n×m的网格,在网格中每次在不超过边界的情况下可以选择向上、向下、向左、向右移动一格。网格中的一些格子上放置有障碍物,放有......
  • qt的c++环境配置和c++基础【正点原子】嵌入式Qt5 C++开发视频
    QTc++环境配置和c++基础c++环境配置和工程创建  1.配置步骤  2.新建qt工程目录和工程  3.重启qt后打开最近的qt项目c++基础-类和对象  1.什么是类和对象    A.类的定义    B.类的结构表示    C.类的访问权限    D.对象的定义    E.类和......
  • 什么时候用C而不用C++
    在选择编程语言时,我们可能会在C和C++之间犹豫。C语言通常用于低级别的系统编程、嵌入式系统开发、操作系统组件、与硬件密切相关的软件、对性能要求极高的应用以及早期使用C语言编写且维护成本较低的项目。而C++以其面向对象特性、灵活的抽象能力、类和模板等特性而广泛应用于软......
  • C++中结构体是使用实例还是指针
    在C++中,结构体(struct)可以通过指针或直接实例来定义。选择使用指针或直接实例化结构体取决于几个因素,包括内存管理、性能、语义和使用场景。以下是一些常见的考虑因素:1. 内存管理:指针:使用指针时,结构体的实例通常在堆上分配。这允许动态管理内存,可以在运行时决定结构体的......
  • 【OJ题解】C++ 把字符串转换成整数
    ......
  • 【C/C++】4.C++的内存管理
    1.C++内存区域   C++程序的内存通常分为以下几部分:栈区(Stack):栈用于存储局部变量、函数参数等临时数据。当函数调用时会为局部变量自动分配栈内存,函数结束后会自动释放。栈的内存分配速度很快,但空间有限。堆区(Heap):堆用于动态分配内存。程序员可以在运行时申请内存,当不......