Multiple C++ Solutions with Explaination
1) Using 2 variables high and low\nThis is a sort of DP solution where we store the profits at each day\n\n\nclass Solution {\npublic:\n    int maxProfit(vector
**1) Using 2 variables high and low**\nThis is a sort of DP solution where we store the profits at each day\n\n```\nclass Solution {\npublic:\n    int maxProfit(vector<int>& prices) {\n        int high=0,low=0;\n        int n = prices.size();\n        \n        //Edge Case\n        if(n<2) return 0;\n        \n        //Store Profits at each day\n        vector<int> profit(n,0);\n        \n        high = prices[0];\n        low = prices[0];\n        \n        //For each day\n        for(int i=1;i<n;i++) {\n            \n            //If current day price is grater then Great! Your profit is increasing\n            if(prices[i]>high) {\n                high = prices[i];\n                profit[i] = high-low;\n            }\n            \n            //If you see a new low- you should reset low as this current price and high as 0\n            //As there can be a bigger margin profit ahead\n            if(prices[i]<=low) {\n                profit[i] = high-low;\n                low = prices[i];\n                high = 0; //Reset\n            }\n            \n            //For cases where the value is between low and high\n                profit[i] =high-low;\n        }\n        \n        return *max_element(profit.begin(),profit.end());\n    }\n};\n```\n\n\n\n**2) Using Max Difference (Unknown Author)**\nThis also uses 2 variables.\n```\nclass Solution {\npublic:\n    int maxProfit(vector<int>& prices) {\n        \n        int min=INT_MAX,maxdiff=0;\n        for(int i=0;i<prices.size();i++)\n        {\n            if(prices[i]<min)\n                min=prices[i];\n            else\n                if(prices[i]-min > maxdiff)\n                    maxdiff = prices[i]-min;\n        }\n        \n        \n        return maxdiff;\n    }\n};\n```\n\n\n**3) Kadane\'s Algorithm**\n\nCheck this [solution](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/discuss/39038/Kadane\'s-Algorithm-Since-no-one-has-mentioned-about-this-so-far-:)\n\n\n**4) Justification for it to be a DP solution**\nCheck this [post](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/discuss/39112/Why-is-this-problem-tagged-with-"Dynamic-programming"/36893)\n
[]