Positive OR negative sign
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime Complexity: O(n)\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSpace Complexity: O(n)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n\n    long long max_cost(int i,int sign, vector<int>&nums, int n,vector<vector<long long>> &dp){\n        //base\n        if(i==n){\n            return 0;\n        }\n        if(dp[i][sign]!=-1){\n            return dp[i][sign];\n        }\n        long long pos=LLONG_MIN,neg=LLONG_MIN;\n        if(sign==0){\n            pos=nums[i]+max_cost(i+1,1,nums,n,dp);\n        }else{\n            if(sign==1){\n                pos=nums[i]+max_cost(i+1,1,nums,n,dp);\n                neg=nums[i]*-1+max_cost(i+1,0,nums,n,dp);\n            }else{\n                pos=nums[i]+max_cost(i+1,1,nums,n,dp);\n            }\n        }\n        return dp[i][sign]=max(pos,neg);\n    }\n    long long maximumTotalCost(vector<int>& nums) {\n        int n=nums.size();\n        vector<vector<long long>>dp(n,vector<long long>(2,-1));\n        long long ans=max_cost(0,0,nums,n,dp);\n        return ans; \n    }\n};\n```
['C++']