✅☑️ Best C++ 3 solution || DP || Space optimization || Brute Force -> Optimize.
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can solve this problem using Three approach.\n\n1. Solved using Array(Two Nested Loo
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can solve this problem using Three approach.\n\n1. Solved using Array(Two Nested Loop). Brute Force Approach.\n2. Solved using Dynamic Programming Approach (tabulation).\n3. Solved using Dynamic Programming Approach(Space optimization).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can easily understand the All the approaches by seeing the code which is easy to understand with comments.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime complexity is given in code comment.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSpace complexity is given in code comment.\n\n# Code\n\n```\n/*\n\n    Time Complexity : O(N^2), Where N is the size of the Array(prices). As we check for possible pair, and the\n    total number of pairs are : N*(N\u20131)/2.\n\n    Space complexity : O(1), Constant space.\n\n    Using Array(Two Nested Loop). Brute Force Approach.\n\n    Note : This will give TLE.\n\n*/\n\n\n/***************************************** Approach 1 Code *****************************************/\n\nclass Solution {\npublic:\n    int maxProfit(vector<int>& prices) {\n        int n = prices.size(), maxProfit = 0;\n        for(int i=0; i<n-1; i++){\n            for(int j=i+1; j<n; j++){\n                if(prices[j] - prices[i] > maxProfit){\n                    maxProfit = prices[j] - prices[i];\n                }\n            }\n        }\n        return maxProfit;\n    }\n};\n\n\n\n\n\n\n/*\n\n    Time Complexity : O(N), As we iterate the array(prices) two times. Where N = size of the array.\n\n    Space complexity : O(N), Array(maxPrices) space.\n\n    Solved using Dynamic Programming Approach(tabulation).\n\n*/\n\n\n/***************************************** Approach 2 Code *****************************************/\n\nclass Solution {\npublic:\n    int maxProfit(vector<int>& prices) {\n        int n = prices.size();\n        vector<int> maxPrices(n, 0);\n        maxPrices[n-1] = prices[n-1];\n        for(int i=n-2; i>=0; i--){\n            maxPrices[i] = max(maxPrices[i+1], prices[i]); \n        }\n        int maxProfit = 0;\n        for(int i=0; i<n; i++){\n            maxProfit = max(maxProfit, maxPrices[i] - prices[i]); \n        }\n        return maxProfit;\n    }\n};\n\n\n\n\n\n\n/*\n\n    Time Complexity : O(N), As we iterate the array(prices) two times. Where N = size of the array.\n\n    Space Complexity : O(1), Constant space.\n\n    Solved using Dynamic Programming Approach(Space optimisation).\n\n*/\n\n\n/***************************************** Approach 3 Code *****************************************/\n\nclass Solution {\npublic:\n    int maxProfit(vector<int>& prices) {\n        int n = prices.size();\n        int buyAtPrice = INT_MAX;\n        int maxProfit = 0;\n        for(int i=0; i<n; i++){\n            buyAtPrice = min(buyAtPrice, prices[i]);\n            maxProfit = max(maxProfit, prices[i] - buyAtPrice); \n        }\n        return maxProfit;\n    }\n};\n\n\n```\n*IF YOU LIKE THE SOLUTION THEN PLEASE UPVOTE MY SOLUTION BECAUSE IT GIVES ME MOTIVATION TO REGULARLY POST THE SOLUTION.*\n\n![WhatsApp Image 2023-02-10 at 19.01.02.jpeg](https://assets.leetcode.com/users/images/0a95fea4-64f4-4502-82aa-41db6d77c05c_1676054939.8270252.jpeg)\n\n\n\n\n
['Array', 'Dynamic Programming', 'C++']