Best Time to Buy & Sell Stocks with Transaction Fee

#include <bits/stdc++.h>
using namespace std;

void getMaxProfitInfiniteTransactionWithFee(int level, int transactionOpen, int profit, int &maxProfit, vector<int> &prices, int fee){

    if(level >= prices.size()){
        maxProfit = max(maxProfit, profit);
        return;
    }
    //levels - each stock price
    //options - buy, sell or don't do anything

    // transaction opened / buying
    if(!transactionOpen){
        getMaxProfitInfiniteTransactionWithFee(level + 1, 1, profit - prices[level], maxProfit, prices, fee);
    }

    //transaction closed / selling
    if(transactionOpen){
        getMaxProfitInfiniteTransactionWithFee(level + 1, 0, profit + prices[level] - fee, maxProfit, prices, fee);
    }

    //Don't do anything / neither buy nor sell
    getMaxProfitInfiniteTransactionWithFee(level + 1, transactionOpen, profit, maxProfit, prices, fee);

}

int getMaxProfitInfiniteTransactionWithFeeMemo(int level, int transactionOpen, vector<int> &prices, int fee, vector<vector<int> > &memo){

    if(level >= prices.size()){
        return 0;
    }

    if(memo[level][transactionOpen] != -1){
        return memo[level][transactionOpen];
    }

    //levels - each stock price
    //options - either buy, sell or don't do anything

    int bought = 0, sold = 0, na = 0;

    //buy only if no transaction opened
    if(!transactionOpen){
        bought += getMaxProfitInfiniteTransactionWithFeeMemo(level + 1, 1, prices, fee, memo) - prices[level];
    }

    //sell only if a transaction is open
    if(transactionOpen){
        sold += getMaxProfitInfiniteTransactionWithFeeMemo(level + 1, 0, prices, fee, memo) + prices[level] - fee;
    }

    // don't do anything
    na = getMaxProfitInfiniteTransactionWithFeeMemo(level + 1, transactionOpen, prices, fee, memo);

    return memo[level][transactionOpen] = max(na, max(bought, sold));

}


int getMaxProfitInfiniteTransactionWithFeeDP(vector<int> &prices){
    /*
    Storage & Meaning - dp[i][0] = processing/decision made upto ith level where the transaction ends as closed
                        dp[i][1] = processing/decision made upto ith level where the transaction ends as open

                        dp[i][0] = decision made upto (i - 1)th level and the ith level ends with 0/sell state
                        dp[i][1] = decision made upto (i - 1)the level and the ith level ends with 1/buy state
    */

    /*
    Direction -

        Identify where the smaller subproblems and larger subproblems lie. To do this see what is the base case.
        In string DP you can do it from either side, but it is convenient to start from 0th index, as definition will make more sense then.

        When you start from left OR from 0th level, generally the subproblems are defined as 'upto ith index ending with char/item/0' and when you start from right OR from (N - 1)th level, subproblems are defined as 'starting from ith index with starting char/item/0'

        You will already have answers to smaller subproblems, now you need to explore all the options at previous level for the current level, to see where the arrows will land at.

        You need to be able to fill all the cells corresponding to the current level.
        FOR 1D dp dp[i]... you need to be able to fill the cell dp[i]

        FOR 2D dp dp[i][j]... you need to be able to fill the cell dp[i][0] upto dp[i][j]

        Simply go to just previous states, define them what they, explore the options, [as you explored the options at a level {(i - 1), or some dp[i - 1][j], you will simply move to the next level{(i), dp[i][?], you just need to figure out what dp cell it will fall in at the next level, figure out the ?]. You can figure it out by attaching the option to the meaning of (i - 1) and see what new meaning it has.

        For eg -
        consider question AiBjCk
        dp[i][a] = Stores all the VALID subsequences ENDING with a, when the DECISION is made upto level i.
        dp[i][b] = Stores all the VALID subsequences ENDING with b, when the DECISION is made upto level i.
        dp[i][c] = Stores all the VALID subsequences ENDING with c, when the DECISION is made upto level i.


        we need to be able to fill any ith level COMPLETELY, EVERY CELL defined at ith level. So the level variable here is i. So we need to be able to fill dp[i][a], dp[i][b], dp[i][c]

        To do this go the past level, here (i - 1)[it can be i - 1, or i - 2, just see the recursion code, what are jumps made to the next level (if there is level + 1, level + 2, ..you need to see what all paths from every past level, if we explore the options for arr[i], string[i], item[i])]

        In the above question AiBjCk, we are jumping atmost level + 1 in any call, so we just need to explore only the (i - 1)th level, if we are to find answers for ith level.


        dp[i - 1][a] = all the valid subsequences ending with a, when decision is made upto (i - 1)th level.
        And similarly for dp[i - 1][b] and dp[i - 1][c]. As you are doing DP, you would already have this table filled up for these cells.

        What you have to do now is to explore the options which are available at ith level, and explore it here.

        for eg - imagine the string was abcbabc, and current ith level is at index 3, that is string[i] = 'b'.

        AAYEGA YA NAHI AAYEGA (simple choice for a subsequence)
        The options available at each level is to -
        include the character or exclude the character
        OR
        Select the character or don't select the character
        OR
        Either character part of subsequence or not the part of subsequence

        So for filling up dp[i][b], explore the option 'b' at the previous level so that you can land on the current level.

        dp[i][a] stores the answer AFTER it has processed the ith level/char, and you land up on ith level only when you would have explored it at previous state.

        So if ith char is 'b', we would be the option available at the previous level (i - 1) is to either include or exclude b



                          dp[i][a]      (exclude b)
                        -
                      -
                    -
        dp[i - 1][a]
                    -
                      -
                        -
                          dp[i][b]      (include b)


        So doing this for all past states, we get

                            dp[i][b]      (exclude b)
                        -
                      -
                    -
        dp[i - 1][b]
                    -
                      -
                        -
                          dp[i][b]        (include b)



                            dp[i][c]      (exclude b)
                        -
                      -
                    -
        dp[i - 1][c]
                    -
                      -
                        -
                          [INVALID CASE]  (include b)


        [INVALID CASE] as - dp[i - 1][c] contains all the subsequences that ends with 'c'. Now you explored the option to include 'b', which means 'b' will be added at the end of the subsequences making all the subsequences end with 'b',  that was already ending with 'c' at the previous level, which will make subsequences of type aabcb, abcb, aabbbccb, which are all invalid cases.

        During Recursion we managed to avoid this invalid call by adding a condition s[lastChar] <= s[level], so that if the last char was a, we can call to a,b or c depending on what char lies at current level.
        If last char was b, we can only call to b & c, and if last char was c, we can only call to c to only have valid subsequences at every level.

        If current character s[i] = 'b', the answer will be filled in dp[i][b], and to form the answer dp[i][b]
        Option available at the previous level, either to include b or exclude b.
        We see what all paths lead to dp[i][b], from all previous levels dp[i - 1][a], dp[i - 1][b], dp[i - 1][c].

        According to the diagram, 1 path from dp[i - 1][a] (option - if b included, now string will end with b)
                                  2 paths from dp[i - 1][b] (both option available, as string will end with b only)
                                  0 paths from dp[i - 1][c] (1 option leads to dp[i][c], other is invalid)



        [INVALID case] =
        dp[i- 1][c] = agar (i - 1)th level/index padi hui saari subsequences jo 'c' se end hoti hai agar uske aage mai 'b' laga du(include b), to mujhe vo saari subsequences milengi ith level/index pe jo 'b' se end hogi. But 'b' se pehle vo 'c' pe end ho rahi thi, to 'b', 'c' ke baad aaya jiske kaaran subsquence invalid ho jaayega according to question.



        We will compute this for every possible character -

        IF s[i] = a, then we will fill dp[i][a], options at previous level = either include 'a' or exclude 'a'

                            dp[i][a]      (exclude a)
                        -
                      -
                    -
        dp[i - 1][a]
                    -
                      -
                        -
                            dp[i][a]      (include a)



                            dp[i][b]      (exclude a)
                        -
                      -
                    -
        dp[i - 1][b]
                    -
                      -
                        -
                            [INVALID case]  (include a)



                            dp[i][c]       (exclude a)
                        -
                      -
                    -
        dp[i - 1][c]
                    -
                      -
                        -
                            [INVALID case]      (include a)



        dp[i][a] = dp[i - 1][a] + dp[i - 1][a] + 1  (1 would be there as subsquence a is allowed)
        dp[i - 1][a] = If we don't select the current char 'a' at level i, still the subsequences will be ending with a

        dp[i - 1][a] = If we select current char 'a', the subsequences will end with a.

        1 = the current character itself is a valid subsequence.

        dp[i][a] =
        dp[i - 1][a] = i - 1 level tak ka decision lene ke baad vo saari subsequences jo 'a' se end hoti hai, uske aage mai current level(ith level) waala 'a' na lagaon, tab bhi mujhe 'a' se end hone waali subsequences milengi, after making decisions upto ith level which is nothing but dp[i][a].

        dp[i - 1][a] = i - 1 level tak ka decision lene ke baad vo saari subsequences padi hai yaha pe jo 'a' se end hoti hai, uske aage mai agar current level waala 'a' laga du, ith level ka decision lene tak /process karne ke baad, mujhe 'a' se end hone waali subsequences milengi.

        1 = vo current level waala 'a' khud ek valid subsequence hai






        IF s[i] = 'c' then we will fill dp[i][c], options at previous level = either include 'c' or exclude 'c'


                            dp[i][a]      (exclude c)
                        -
                      -
                    -
        dp[i - 1][a]
                    -
                      -
                        -
                            [INVALID CASE]      (include c)



                            dp[i][b]      (exclude c)
                        -
                      -
                    -
        dp[i - 1][b]
                    -
                      -
                        -
                            dp[i][c]      (include c)



                            dp[i][c]      (exclude c)
                        -
                      -
                    -
        dp[i - 1][c]
                    -
                      -
                        -
                            dp[i][c]      (include c)



        so dp[i][c] = dp[i - 1][c] + dp[i - 1][c] + dp[i - 1][b]


        dp[i - 1][c] = agar i - 1th level pe 'c' se end hone waali subsequences ke aage agar mai current level waala 'c' na lagaon to merko 'c' se end hone waali subsequences milengi ith level par
        dp[i - 1][c] = agar i - 1th level pe 'c' se end hone waali subsequences ke aage agar mai current level waala 'c' laga du to to 'c' se end hone waali subsequences hi milengi ith level par
        dp[i - 1][b] = agar i - 1th level pe 'b' se end hone waali saari subsequences ke aage mai 'c' laga du, to mujhe vo saari subsequences mil jaayengi jo 'c' se end hogi ith level par.


        For any dp[i][j], identify what all smaller states could have made the answer for the current state,
        analyse all the valid options at previous level(here, i - 1) and when you explore an option [that is when
        you make a recursive call from a level to the next level]

        In recursion when you are on a level, you analyse what all VALID options are(sudoku, binary strings)
        and then you try to explore each option by making a recursive call, which takes you to the next level.


    */
}

int main() {
    // your code goes here
    int n, fee;
    cin >> n;
    vector<int> prices(n);
    for(int i = 0; i < n; i++){
        cin >> prices[i];
    }
    cin >> fee;
    /*
    RECURSION CALL
        int maxProfit = 0;
        getMaxProfitInfiniteTransactionWithFee(0, 0, 0, maxProfit, prices, fee);
        cout << maxProfit << '\n';
    */

    /*
    MEMO CALL


    */
    vector<vector<int> > memo(n, vector<int>(2, -1));
    cout << getMaxProfitInfiniteTransactionWithFeeMemo(0, 0, prices, fee, memo) << '\n';
}