题解 | #风口的猪-中国牛市#Java&&C++（小白向）
风口的猪-中国牛市
https://www.nowcoder.com/practice/9370d298b8894f48b523931d40a9a4aa
本题用动态规划求解，题解写的人少，费时间，请多多点赞
因为之前做过求单次最大套利多少的题，所以下意识想分情况讨论
之前写的文章
先说一下一次买入的收益计算方法
设dp[n][2] dp[n][0] 为未持有股票时第n天的持有的 最大 金额
dp[n][1]为第n天持有股票时所持有的 最大 金额
状态转移方程为
dp[n][0] = max(dp[n-1][0], dp[n-1][1]+price[n])
如果第n天未持有股票，金额分为两种情况 :一种是之前未买入和之前已经卖出的
今天卖出的值，取最大
dp[n][1] = max(dp[n-1][1], -price[n])
如果第n天持有股票，金额分为两种情况:
一种仍然持有不卖出
一种是今天卖出，取最大
这里取最大的原因是 花费的越少后面赚的越多
综上我就想着再设一个dp记录第二次的，但是没实现，当时没想到解决将第一次的值映射的到第二次两者同步的方法，所以参考了‘卖萌の哈士奇’大佬的题解,更新了下思路
设置两个dp1，dp2，分别记录第0 到第 i天最大的获利情况，和第i天到最后一天的最大获利，最后结果为dp1[i]+dp2[i]相加的最大值，这样就解决了同步问题
第一次买卖 代码很清晰 ，关键在第二次 ，
dp2之所以从反方向遍历而来，是因为动态规划初值设定非常重要，
但是dp2[0]并不能确定，而dp2最后一个元素一定能确定 ,
因为如果第一次卖出是在最后一天，那么第二次买卖不能实施，第二次买卖的最大值为0
（c++初学，记录一下错误，max中不能比较vector和int ， memset（a,b,c）的c参数是字节的长度，不是数组的长度，int n[10] 要填40而不是10，建议还是用sizeof （
#include <bits/stdc++.h>
#include <vector>
class Solution {
public:
/**
* 计算你能获得的最大收益
*
* @param prices Prices[i]即第i天的股价
* @return 整型
*/
int calculateMax(std::vector<int> prices) {
int ans = 0;
int days = prices.size();
int ndp[days];
int rdp[days];
memset(ndp, 0, sizeof (ndp));
memset(rdp, 0, sizeof (rdp));
int minValue = prices[0];
for (int i = 1; i < days; i++) {//第一次正向遍历
if (prices[i] - minValue > ndp[i - 1]) {
ndp[i] = prices[i] - minValue;
} else {
ndp[i] = ndp[i - 1];
}
if (minValue > prices[i]) {
minValue = prices[i];
}
}
int maxValue = prices[days - 1];
for (int i = days - 2; i >= 0 ; i--) {//第二次反向遍历
if ((maxValue - prices[i]) > rdp[i + 1] ) {
rdp[i] = maxValue - prices[i];
} else {
rdp[i] = rdp[i + 1];
}
if (maxValue < prices[i]) {
maxValue = prices[i];
}
}
for (int i = 0; i < days; i++) {
if (ans < ndp[i] + rdp[i]) {
ans = ndp[i] + rdp[i];
}
}
return ans;
}
};
import java.util.*;
public class Solution {
/**
* 计算你能获得的最大收益
*
* @param prices Prices[i]即第i天的股价
* @return 整型
*/
public int calculateMax(int[] prices) {
int ans = 0;
int days = prices.length;
int[] ndp = new int[days];
int[] rdp = new int[days];
int min = prices[0];
ndp[0] = 0;//第一次正向遍历
for (int i = 1; i < days; i++) {
if (prices[i] -min > ndp[i-1]){
ndp[i] = prices[i]-min;
}else {
ndp[i] = ndp[i-1];
}
min = Math.min(min,prices[i]);
}
int max = prices[days-1];//第二次反向遍历
for (int i = days-2; i >= 0 ; i--) {
if ((max - prices[i]) > rdp[i+1] ){
rdp[i] = max-prices[i];
}else {
rdp[i] = rdp[i+1];
}
max = Math.max(max,prices[i]);
}
for (int i = 0; i < days; i++) {
ans = Math.max(ans,ndp[i]+rdp[i]);
}
return ans;
}
}
动态规划题解 文章被收录于专栏
个人动态规划题解合集
投递淘天集团等公司10个岗位 >
