2015小米暑假笔试题

题目链接:https://www.nowcoder.com/question/next?pid=24585&qid=23494&tid=27265371

2015小米暑假笔试题

 

 分析:最初我是想定义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]的最大值

2015小米暑假笔试题

 

 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;
    }
};

如果有不清楚的欢迎留言讨论。。

上一篇:P1880-[NOI1995]石子合并


下一篇:The Number of Products