Recursion + Memo
Function used in the recursion will  have the following parameters.\n\npos - postion in the array\nstat - whether a subarray is already under construction or no
Function used in the recursion will  have the following parameters.\n\npos - postion in the array\nstat - whether a subarray is already under construction or not.\nsign - The sign of the current element if its added to the subarray \n\n-----\n\nWe can use a memo of the form dp[100001][2][2]\n(make sure the dp is initialized to -1e16 and not -1, as -1 is a possible answer)\n\npos<=100000\nstat can have two values 0 and 1(0 - not started, 1 - started)\nsign can have two values 0 and 1(0 implies +ve sign and 1 implies -ve sign)\n\n-----\n\nWe get a unique state using these parameters. \nRecursion calls are explained in the code. \n\n(please upvote if it helped)\n\n# Code\n```\n#define ll long long\n\nll find(int pos, int stat, int sign, vector<ll> &nums, vector<vector<vector<ll>>> &dp)\n{\n    if(pos == nums.size())\n        return 0;\n    \n    ll ans = -1e15;\n    \n    if(dp[pos][stat][sign]!=-1e16)\n        return dp[pos][stat][sign];\n    \n    if(stat == 0) // we have to start the construction of a new subarray\n        ans = max(ans, nums[pos] + find(pos+1, 1, 1, nums, dp)); // start the construction with sign = 1 as the next element will have negetive sign\n    \n    else if(stat == 1) // A subarray is already under construction\n    {\n        if(sign == 1) // negetive sign\n        {\n            ans = max(ans, -nums[pos] + find(pos+1, 1, 0, nums, dp)); // continue construction with flipped sign\n            ans = max(ans,  find(pos, 0, 0, nums, dp)); // end the construction and begin a new one at this index. Dont increase pos, just change stat to 0.\n        }\n    \n        else if(sign == 0) // positive sign\n        {\n            ans = max(ans, nums[pos] + find(pos+1, 1, 1, nums, dp)); // continue construction with flipped sign\n            ans = max(ans, find(pos, 0, 0, nums, dp));  // end the construction and begin a new one at this index. Dont increase pos, just change stat to 0.\n        }\n    }\n\n    return dp[pos][stat][sign] = ans;\n}\n\nclass Solution {\npublic:\n    long long maximumTotalCost(vector<int>& nums) {\n\n        vector<ll> t1(2, -1e16);\n        vector<vector<ll>> t2(2, t1);\n        vector<vector<vector<ll>>> dp(nums.size()+1, t2); //initializing to -1e16\n    \n        vector<ll> a(nums.begin(), nums.end()); // converted to long long just in case, to avoid overflow any kind of overflow.\n\n        ll ans = find(0, 0, 0, a, dp);\n        return ans;\n    }\n};\n    \n\n    \n```
['C++']