动态规划练习(1)--[编程题] 风口的猪-中国牛市

动态规划练习(1)--编程题 风口的猪-中国牛市

动态规划学习参考：

教你彻底学会动态规划——入门篇

https://blog.csdn.net/baidu_28312631/article/details/47418773 

编程题 风口的猪-中国牛市

风口之下，猪都能飞。当今中国股市牛市，真可谓“错过等七年”。 给你一个回顾历史的机会，已知一支股票连续n天的价格走势，以长度为n的整数数组表示，数组中第i个元素（prices[i]）代表该股票第i天的股价。 假设你一开始没有股票，但有至多两次买入1股而后卖出1股的机会，并且买入前一定要先保证手上没有股票。若两次交易机会都放弃，收益为0。 设计算法，计算你能获得的最大收益。 输入数值范围：2<=n<=100,0<=prices[i]<=100 

输入例子1:

3,8,5,1,7,8

输出例子1:

12

思路：
正序遍历得到第k天之前可以获得的最大收益，后序遍历得到第k天后面可以获得的最大收益。

状态转移方程：

pmax[i] = max( pmax[i-1], arr[i] - premin )    //k天前最大收益

pmax[i] = max ( pmax[i+1], premax - arr[i] )   //k天后最大收益

class Solution {
public:
    /**
     * 计算你能获得的最大收益
     * 
     * @param prices Prices[i]即第i天的股价
     * @return 整型
     */
    int calculateMax(vector<int> prices) {
        int n=prices.size();
        
        int premin=prices[0];
        vector<int> leftmax(n);
        leftmax[0]=0;
        for(int i=1;i<n;i++)
        {
            premin=min(premin,prices[i]);
            leftmax[i]=max(leftmax[i-1],prices[i]-premin);
        }
        
        int lastmax=prices[n-1];
        vector<int> rightmax(n);
        rightmax[n-1]=0;
        for(int i=n-2;i>=0;i--)
        {
            lastmax=max(lastmax,prices[i]);
            rightmax[i]=max(rightmax[i+1],lastmax-prices[i]);
        }
        
        int pmax=0;
        for(int i=0;i<n;i++)
        {
            pmax=max(pmax,leftmax[i]+rightmax[i]);
        }
        return pmax;
    }
};