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

// 122. 买卖股票的最佳时机 II---通过
// 执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
// 内存消耗：12.8 MB, 在所有 C++ 提交中击败了16.13%的用户
// 可无数次交易
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int dp[30000][2];
        dp[0][1]=-prices[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];
    }
};


// 123. 买卖股票的最佳时机 III---通过
// 执行用时：4 ms, 在所有 C++ 提交中击败了82.92%的用户
// 内存消耗：10.9 MB, 在所有 C++ 提交中击败了39.83%的用户
// 可2次交易(代码同 188. 买卖股票的最佳时机 IV， 令k=2)


// 188. 买卖股票的最佳时机 IV---通过
// 执行用时：8 ms, 在所有 C++ 提交中击败了79.25%的用户
// 内存消耗：11.3 MB, 在所有 C++ 提交中击败了54.25%的用户
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        if(n<=0) return 0;
        int dp[1000][101][2];
        for(int j=1; j<=k; ++j)
            dp[0][j][1]=-prices[0]; //当成当天可买卖处理 忽略dp[0][0][1]遍历不到
        for(int i=1; i<n; ++i)
        {
            for(int j=1; j<=k; ++j)
            {
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i]);
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i]);
            }
        }
        return dp[n-1][k][0];
    } 
};

// 309. 最佳买卖股票时机含冷冻期---通过
// 执行用时：4 ms, 在所有 C++ 提交中击败了81.13%的用户
// 内存消耗：10.9 MB, 在所有 C++ 提交中击败了81.59%的用户
// 可无数次交易 有一天冷冻期 (代码同122. 买卖股票的最佳时机 II i-1改成i-2隔天交易)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==1) return 0;
        int dp[30000][2];
        dp[0][1]=-prices[0];
        dp[1][0]=max(0,prices[1]-prices[0]);
        dp[1][1]=max(-prices[0],-prices[1]);
        for(int i=2; 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-2][0]-prices[i]);
        }
        return dp[n-1][0];
    }
};


// 714. 买卖股票的最佳时机含手续费---通过
// 执行用时：100 ms, 在所有 C++ 提交中击败了89.62%的用户
// 内存消耗：54.1 MB, 在所有 C++ 提交中击败了45.85%的用户
// 可无数次交易(代码同122. 买卖股票的最佳时机，计算收益时减去手续费)