题目链接:https://www.nowcoder.com/question/next?pid=24585&qid=23494&tid=27265371
分析:最初我是想定义f[i][j]来表示i天买股票,第j天卖出所得到的收益,如果这样做的话,之后寻找最大值的时候会出现f[i][j]+f[t][k](i<=j<=t<=k)需要四重循环,应该会爆,我没试
我的目标是找到两次收益和的最大值,并且必须第一个股票卖出才能买入(说的直白就点是第二次买入的时间>=第一次卖出的时间)
所以定义一个dp1[i]表示第i天卖出所得到的最大收益
dp2[i]表示第i天买入所得到的最大收益
所要求的就是dp1[i]+dp[j]的最大值
c++代码如下:
class Solution { public: /** * 计算你能获得的最大收益 * * @param prices Prices[i]即第i天的股价 * @return 整型 */ int calculateMax(vector<int> v) { int dp1[101]={0},dp2[101]={0}; int n=v.size(); for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ int tmp=v[j]-v[i]; dp1[j]=max(dp1[j],tmp); dp2[i]=max(dp2[i],tmp); } } int ans=0; for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ ans=max(ans,dp1[i]+dp2[j]); } } if(ans<0) return 0; return ans; } };
如果有不清楚的欢迎留言讨论。。