Recursion+Memo-Easy Solution-O(n)-Dynamic Programming
Intuition\nSign and index represents the states of dp and if the sign remains 0 means we take the next subarray.\n\n# Approach\nTake or not take approach\n\n# C
# Intuition\nSign and index represents the states of dp and if the sign remains 0 means we take the next subarray.\n\n# Approach\nTake or not take approach\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nusing ll=long long;\nclass Solution {\npublic:\n    ll dp[100001][2];\n    long long int solve(vector<int>&v,int n,int i,int sign){\n        if(i>=n){\n            return 0;\n        }\n        if(dp[i][sign]!=-1){\n            return dp[i][sign];\n        }\n        ll ta=0;\n        ll nt=0;\n        if(sign==0){\n            ta=v[i]+solve(v,n,i+1,1);\n            nt=v[i]+solve(v,n,i+1,0);\n        }\n        else{\n            ta=(-1*v[i])+solve(v,n,i+1,0);\n        }\n        return dp[i][sign]=max<ll>(ta,nt);\n    }\n    long long maximumTotalCost(vector<int>& nums) {\n        int n=nums.size();\n        memset(dp,-1,sizeof(dp));\n        ll f=solve(nums,n,0,0);\n        return f;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']