网站建站要交税吗,wordpress 活动插件,河南中国建设银行官网站,旅游app用户人群分析cpp买卖股票 前言题目示例 1:示例 2:示例 3:题目分析#xff1a; 代码及思路简单版动态规划版 前言
今天继续跟着小浩老师学习算法#xff0c;由易到难#xff0c;感觉越来越有意思啦。今天学习算法中的经典问题#xff0c;股票的买卖。我所用的是非常简单的思路#xff… cpp买卖股票 前言题目示例 1:示例 2:示例 3:题目分析 代码及思路简单版动态规划版 前言
今天继续跟着小浩老师学习算法由易到难感觉越来越有意思啦。今天学习算法中的经典问题股票的买卖。我所用的是非常简单的思路后续学习了动态规划的思想其实大二的时候学算法分析与设计这门课的时候就似懂非懂很多东西妹学明白今天做的这道动态规划的题我感觉不难而且还蛮有意思的。
题目 给定一个数组它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易即买入和卖出一支股票设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。 示例 1:
输入: [7,1,5,3,6,4]
输出: 7解释: 在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。 随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6-3 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4解释: 在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。
注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出。
因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
题目分析
首先我们看一下题目中给出的两个条件
1、不能参与多笔交易。换句话讲我们只能在手上没有股票的时候买入也就是必须在再次购买前出售掉之前的股票。像我们平时买股票时的追涨杀跌是不可以的。
2、尽可能地多进行交易。这个非常好理解。像是黄金一年基本上都有2-3次涨跌。我们只要把握住机会在每一次涨跌的时候低价卖入高价卖出就可以使利益达到最大化。这个条件也是相当重要的如果我们把这里变成最多完成两笔交易就变成另一道题。 更多的分析请点击小浩算法----买卖股票的最佳时期 题解分析
代码及思路
简单版
其实最开始我自己的思路挺简单的能实现这个功能。 我的思路就是 从第一个元素开始如果这个元素的后一天的价格大于当前天的价格那么就卖出去积攒利润否则就继续遍历直到倒数第二个元素这里如果到最后一个会有内存泄漏的问题 挺简单的对叭哈哈哈哈真的好简单 值得注意的是在cpp里面我们使用vector可以在初始化的时候不指定大小但是需要注意格式。我太爱vector了呵呵
#includeiostream
#includevector
using namespace std;
int main() {cout 请输入总天数: endl;int amountDays;cin amountDays;int priceDay;//指定一个空的vectorvectorint stockPriceArray;//先输入股票的价格for (int i 0; i amountDays; i) {cin priceDay;stockPriceArray.push_back(priceDay);}//初始化总利润价格为0元int amountPrice0;//如果遇到第二天比第一天高,那么就买了在卖,这就是最大的利润for (int i 0; i amountDays-1; i) {if (stockPriceArray[i] stockPriceArray[i 1]) {amountPrice amountPrice stockPriceArray[i 1] - stockPriceArray[i];}}cout amountPrice endl;return 0;
}动态规划版
动态规划的思想其实最核心的是我当前的状态的值和我的上一个状态是息息相关的所以我们需要考虑两个问题 我的初始值是什么前一个状态和后一个状态之间的联系怎么确立 废话不多说由于我们最后要求的是利润而且每一天我们都可以选择抛售or保留股票这样下来每天的不同状态下的利润都是不一样的。
如果我在第i天我的手上有股票那么我当天的利润值应该分为两个部分①我前一天有股票今天没卖出去 利润等于前一天有股票的利润② 我前一天没有股票今天买进来了前一天没有股票的利润 - 今天的股票价格如果我在第i天手上没有股票那么当天的利润值也应该有两种情况。①我前一天就没有股票利润和前一天没有股票一样 ② 我前一天有股票今天卖了利润应该等于前一天有股票的利润 今天股票的价格 有没有人觉得这个东西好像神经网络的结构因此我们可以用二维数组来解决上面这个问题。需要设置初始值很容易知道 [0][0]位置是第一天不拥有股票则利润是0那[0][1]则是第一天拥有股票利润是-price[1]
#includeiostream
#includevector
using namespace std;
int main() {cout 请输入总天数: endl;int amountDays;cin amountDays;int priceDay;//指定一个空的vectorvectorint stockPriceArray;//先输入股票的价格for (int i 0; i amountDays; i) {cin priceDay;stockPriceArray.push_back(priceDay);}//设置一个二维数组,对于vector用嵌套来设置,行是第一个形参,列是第二个形参vectorvectorint dp(stockPriceArray.size(), vectorint(2));//初始化dp[0][0] 0;dp[0][1] -stockPriceArray[0];for (int i 1; i amountDays; i) {dp[i][0] max(dp[i - 1][0], dp[i-1][1] stockPriceArray[i]);dp[i][1] max(dp[i - 1][1], dp[i - 1][0] - stockPriceArray[i]);}cout dp[amountDays-1][0] endl;return 0;}好好加油要学会努力地提升自己coding的能力把技术学好加油加油
