题解 | 买卖股票的最好时机(一)

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        vector<int>prices(n);
        for(int i=0;i<n;i++){
            cin>>prices[i];
        }
        // int profit=0;
        // for(int i=0;i<n;i++){
        //     for(int j=i+1;j<n;j++){
        //         if(prices[j]>prices[i]){
        //             profit=max(profit,prices[j]-prices[i]);
        //         }
        //     }
        // }
        // cout << profit << endl;
        //O(n2)超时

        //动态规划
        //将prices转化为涨跌幅，然后用最大连续和求，这样就是两个O(n)的操作了

        vector<int>dis(n+1);
        dis[0]=0;
        for(int i=1;i<=n;i++){
            dis[i]=prices[i]-prices[i-1];
        }
        vector<int>dp(n,0);
        int profit=0;
        for(int i=1;i<n;i++){
            dp[i]=max(dp[i-1]+dis[i],dis[i]);
            profit=max(profit,dp[i]);
        }
        cout<<profit<<endl;

        //贪心算法
        //维护一个minprice和一个maxprofit
        //因为要求后大减前小，后面的利润组合一定是当前prices和新的minprice得到的
        // int minprice=prices[0];
        // int maxprofit=0;
        // for(int i=1;i<n;i++){
        //     if(prices[i]<=minprice){
        //         minprice=prices[i];
        //     }
        //     else{
        //         maxprofit=max(maxprofit,prices[i]-minprice);
        //     }
        // }
        // cout<<maxprofit<<endl;
    }
  return 0；
}
// 64 位输出请用 printf("%lld")