DP Approach | Memoization | Tabulation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nWe can consider this problem as a dp problem of Pattern Take/notTake, whe
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nWe can consider this problem as a dp problem of Pattern Take/notTake, where our Take is Positive value and not Take is our negative value. We can use a bool variable to check whether our curr idx can have negative or not.\n\n# Memoization Approach\n```\nll solve(vector<int> &nums, int i, bool neg, vector<vector<ll>> &dp){\n\n        // out of bounds \n        if(i >= nums.size())\n            return 0;\n        // if pre calculated return the val.\n        if(dp[i][neg] != -1e9)\n            return dp[i][neg];\n        // take/ negtake cases\n        ll negTake  = -1e8, take = -1e8;\n\n\n        // if we have previously taken a positive value\n        // we can take curr as negative\n        if(neg){\n            negTake = (-nums[i]) + solve(nums, i + 1, false, dp);\n        }\n        // we take this as new subarray and make neg == true\n        for the next element to be counted in the same subarray.\n\n        take = (nums[i]) + solve(nums, i + 1, true, dp);\n\n        // returning the ans;\n        return dp[i][neg] = max(take, negTake);\n\n\n    }\n\n    public:\n    long long maximumTotalCost(vector<int>& nums) {\n        int n = nums.size();\n\n        vector<vector<ll>> dp(n, vector<ll> (2, -1e9));\n        int i = 1; bool neg = true;\n        return (ll) nums[0] + solve(nums, i, neg, dp);\n    }\n```\n\n## Why Taking first element by default and negative as 1 in starting?\n\nWe are here taking first element as default because we have to take first element in exactly one subarray and it will start from first element only.\n\nAs for why negative == 1 since we already consider our first subarray we are checking whether the next elements will be a part of same subarray or we have to take it in another subarray\n\n# Tabulation Approach\n\n```\n#define ll long long\n\nclass Solution {\n    \npublic:\n    long long maximumTotalCost(vector<int>& nums) {\n        int n = nums.size();\n\n        vector<vector<ll>> dp(n, vector<ll> (2, 0));\n        dp[0][1] = dp[0][0] = nums[0];\n        for(int i = 1; i<n; i++){\n            for(int j = 0; j<2; j++){\n                ll negTake = -1e5, take = -1e5;\n                if(j == 1){\n                    negTake = (-nums[i] + dp[i-1][0]);\n                }\n                take = (nums[i] + dp[i-1][1]);\n                dp[i][j] = max(take, negTake);\n            }\n        }\n\n        return dp[n-1][1];\n    }\n};\n```\n\n# Complexity\n- Time complexity:O(N * 2)\n\n- Space complexity: O(N)
['Dynamic Programming', 'Memoization', 'C++']