DP: Recursion Memo-> tabular with space O(1)||46ms beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nTry DP.\nUse Recursion with Memo-> Tabular with optimized space.\n# Approach\n Describe
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTry DP.\nUse Recursion with Memo-> Tabular with optimized space.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Define recursive function `long long  f(int i, bool minus, vector<int>& nums)` with cache `long long  dp[100000][2]`\n2. The recursive relations are as follows\n```\nsum=((!minus)? nums[i]: -1*nums[i]) + f(i+1, !minus, nums);\nsum= max(sum, nums[i] + f(i+1, 1, nums));\n```\n3. 2nd code is a conversion from recursive version into an iterative version in which the space need is reduced by `&1` trick\n```\nfor(int i=n-1; i>=0; i--){\n    long long x=nums[i];\n    dp[i&1][0]=x+dp[(i+1)&1][1];\n    dp[i&1][1]=-x+dp[(i+1)&1][0];\n    dp[i&1][0]=max(dp[i&1][0], x+dp[(i+1)&1][1]);\n    dp[i&1][1]=max(dp[i&1][1], x+dp[(i+1)&1][1]);\n}\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n) \\to O(1)$$\n# Code recursive DP|| 59ms beats 100%\n```\nclass Solution {\npublic:\n    int n;\n    long long  dp[100000][2];\n    long long  f(int i, bool minus, vector<int>& nums){\n        if(i == n) return 0;\n        if(dp[i][minus] != LONG_MIN) return dp[i][minus];\n        long long  sum=((!minus)?nums[i]:-1*nums[i])+f(i+1, !minus, nums);\n        sum = max(sum, nums[i] + f(i+1, 1, nums));\n        return dp[i][minus] = sum;\n    }\n    \n    long long maximumTotalCost(vector<int>& nums) {\n        n= nums.size();\n        fill(&dp[0][0], &dp[0][0]+2*n, LONG_MIN);\n        return f(0, 0, nums);\n    }\n};\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# C++ iterative DP with O(1) space||49ms beats 100%\n```\nclass Solution {\npublic:    \n    long long maximumTotalCost(vector<int>& nums) {\n        const int n = nums.size();\n        long long dp[2][2]={{0}};\n        for(int i=n-1; i>=0; i--){\n            long long x=nums[i];\n            dp[i&1][0]=x+dp[(i+1)&1][1];\n            dp[i&1][1]=-x+dp[(i+1)&1][0];\n            dp[i&1][0]=max(dp[i&1][0], x+dp[(i+1)&1][1]);\n            dp[i&1][1]=max(dp[i&1][1], x+dp[(i+1)&1][1]);\n        }\n        return dp[0][0];\n    }\n};\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Dynamic Programming', 'C++']