用 f i f_i fi 表示 1 → i 1\to i 1→i 交易一次的最大利润 用 f f i ff_i ffi 表示 1 → i 1\to i 1→i 交易二次的最大利润
class Solution { public: int n,f[100001],ff[100001]; int maxProfit(vector<int>& a) { n=a.size(); memset(f,0,sizeof(f)); int minx=0x3fffffff; for(int i=0;i<n;i++){ f[i]=max(a[i]-minx,0); if(minx>a[i])minx=a[i]; } for(int i=1;i<n;i++)if(f[i]<f[i-1])f[i]=f[i-1]; int maxx=-0x3fffffff; for(int i=0;i<n;i++){ ff[i]=max(a[i]+maxx,0); if(maxx<f[i]-a[i])maxx=f[i]-a[i];//记录那个时候买进来利润的最大值 } int ans=0; for(int i=0;i<n;i++){ if(ans<ff[i])ans=ff[i]; } return ans; } };