百度-测开日常实习-部分手撕代码题【1】

（高频）百度二面：股票的最大利润【中等】

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

（上面这个跟力扣原题不太一样，原题是中等题，是有可以多次买卖的，用例输出答案是7）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sum=0;
        for(int i=1;i<prices.size();i++){
            sum+=max(0,(prices[i]-prices[i-1]));
        }
        return sum;

    }
};

不太会做，试了下贪心，没想到ac了，看了看题解是二维动归，研究研究估计也能做。

——————————————————————

好未来笔试遇到了这个题，纯贪心没过全部用例，再次再复习下二维动归的解法：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = (int)prices.size(), ans = 0;
        int dp[n][n];//d[i][0]代变第i天不持有股票的最大利润   d[i][1]则代表持有的利润
        dp[0][0]=0;//第0天不持有
        dp[0][1]=-prices[0];//第0天持有

        for (int i = 1; i < n; ++i){
            
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
                
                dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
            
        }
        return dp[n-1][0];//要卖出 不持有
    }
};

百度：8. 手撕判断回文串[简单]