<p>You are given an integer array <code>prices</code> where <code>prices[i]</code> is the price of a given stock on the <code>i<sup>th</sup></code> day.</p>

<p>On each day, you may decide to buy and/or sell the stock. You can only hold <strong>at most one</strong> share of the stock at any time. However, you can buy it then immediately sell it on the <strong>same day</strong>.</p>

<p>Find and return <em>the <strong>maximum</strong> profit you can achieve</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> prices = [7,1,5,3,6,4]
<strong>Output:</strong> 7
<strong>Explanation:</strong> Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> prices = [1,2,3,4,5]
<strong>Output:</strong> 4
<strong>Explanation:</strong> Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> prices = [7,6,4,3,1]
<strong>Output:</strong> 0
<strong>Explanation:</strong> There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= prices.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>0 &lt;= prices[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    // int f(int idx, int buy, vector<int>& prices, vector<vector<int>>&dp) {
    //     //bcase
    //     if(idx == prices.size()) {
    //         //ye case tab ayega jab apan buy to karlia but sell nahi kia
    //         return 0;
    //     }

    //     if(dp[idx][buy] != -1) return dp[idx][buy];
    //     if(buy)
    //                                 //cannot buy further             //can buy further
    //         return dp[idx][buy] = max(f(idx+1,0,prices,dp) - prices[idx], 0 + f(idx+1,1,prices,dp));

    //     else {
    //         //not buy i.e sell
    //                                                 //sell                      //not sell
    //         return dp[idx][buy] = max(prices[idx] + f(idx+1,1,prices,dp), 0 + f(idx+1,0,prices,dp));
    //     }
    // }
    // int maxProfit(vector<int>& prices) {   //0 to n-1 wala recursion
    //     int n = prices.size();
    //     vector<vector<int>>dp(n,vector<int>(2,-1));
    //     return f(0,1,prices,dp);
    // }

    // int f(int idx, int buy, vector<int>& prices, vector<vector<int>>&dp) {
    //     //bcase
    //     if(idx == 0) {
    //         if(buy) return -prices[idx];
    //         else return 0;
    //     }

    //     if(dp[idx][buy] != -1) return dp[idx][buy];
    //     if(buy)
    //                     //cannot buy further             //can buy further
    //         return dp[idx][buy] = max(f(idx-1,0,prices,dp) - prices[idx], 0 + f(idx-1,1,prices,dp));

    //     else {
    //         //not buy i.e sell
    //                         //sell                      //not sell
    //         return dp[idx][buy] = max(prices[idx] + f(idx-1,1,prices,dp), 0 + f(idx-1,0,prices,dp));
    //     }
    // }
    // int maxProfit(vector<int>& prices) {   //0 to n-1 wala recursion
    //     int n = prices.size();
    //     vector<vector<int>>dp(n,vector<int>(2,-1));
    //     return f(n-1,0,prices,dp);
    // }

    // int maxProfit(vector<int>& prices) { // 0 to n-1 wala tab - sopt
    //     int n = prices.size();
    //     vector<vector<int>>dp(n,vector<int>(2,0));

    //     dp[0][0] = 0; //0th idx not buy i.e sell but buy ke pehle sell nahi karskte therefore 0
    //     dp[0][1] = -prices[0]; //0th idx buy, buy karna means profit me - karna, sell karna means profit me + karna
    //     for(int idx = 1;idx<n;idx++) {
    //         for(int buy = 1; buy >=0;buy--) {
    //             if(buy)
    //                         //cannot buy further             //can buy further
    //                 dp[idx][buy] = max(dp[idx-1][0]- prices[idx], 0 + dp[idx-1][1]);

    //             else {
    //                 //not buy i.e sell
    //                                 //sell                      //not sell
    //                 dp[idx][buy] = max(prices[idx] + dp[idx-1][1], 0 + dp[idx-1][0]);
    //             }
    //         } 
    //     }
    //     // We should return dp[n-1][0], which means the maximum profit after the last day
    //     return dp[n-1][0]; // YE NAHI AYA DIMAG ME coz mene recursion 0 to n-1 wala likha tha
    // }

    int maxProfit(vector<int>& prices) { //n-1 to 0 wala tab w/o sopt
        int n = prices.size();
        vector<vector<int>>dp(n+1,vector<int>(2,0)); //n+1 ka dp size hai

        dp[n][0] = 0; // from recursion
        dp[n][1] = 0;

        for(int idx = n-1;idx>=0;idx--) {
            for(int buy = 0; buy <=1;buy++) {
                if(buy)
                                        //cannot buy further             //can buy further
                    dp[idx][buy] = max(dp[idx+1][0] - prices[idx], 0 + dp[idx+1][1]);

                else {
                    //not buy i.e sell
                                            //sell                      //not sell
                    dp[idx][buy] = max(prices[idx] + dp[idx+1][1], 0 + dp[idx+1][0]);
                } 
            }
        }
        return dp[0][1]; // intially buy 1 rehta islye dp[0][1] call kia.
    }


    // int maxProfit(vector<int>& prices) {
    //     int n = prices.size();
    //     vector<int>prev(2,0);
    //     vector<int>curr(2,0);

    //     prev[0] = 0; //0th idx not buy i.e sell but buy ke pehle sell nahi karskte therefore 0
    //     prev[1] = -prices[0]; //0th idx buy, buy karna means profit me - karna, sell karna means profit me + karna
    //     for(int idx = 1;idx<n;idx++) {
    //         for(int buy = 1; buy >=0;buy--) {
    //             if(buy)
    //                         //cannot buy further             //can buy further
    //                 curr[buy] = max(prev[0]- prices[idx], 0 + prev[1]);

    //             else {
    //                 //not buy i.e sell
    //                                 //sell                      //not sell
    //                 curr[buy] = max(prices[idx] + prev[1], 0 + prev[0]);
    //             }
    //         } 
    //         prev = curr;
    //     }
    //     // We should return dp[n-1][0], which means the maximum profit after the last day
    //     return prev[0]; // YE NAHI AYA DIMAG ME
    // }
    
};
18000