Simple || DP | Easy | C++ | O(N) | Seven line code | optimal
Intuition\n Describe your first thoughts on how to solve this problem. \nTo maximize the total cost of subarrays, we need to strategically decide where to split
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo maximize the total cost of subarrays, we need to strategically decide where to split the array. The cost of a subarray nums[l..r] alternates between adding and subtracting the elements based on their positions (even-indexed elements are added, odd-indexed elements are subtracted). This gives us two main tasks:\n\nCalculate the cost of continuing the current subarray.\nCalculate the cost of starting a new subarray.\nOur goal is to use dynamic programming to determine the optimal points to split the array to achieve the maximum possible total cost.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Cost Function Understanding:** The cost of subarray nums[l..r] can be broken down as:\nEven indexed elements within the subarray are added.\nOdd indexed elements within the subarray are subtracted.\n\n**Dynamic Programming Setup:**\nUse a 2D DP table dp[i][check] where i represents the current index and check represents the current sign (positive if check is true, negative if check is false).\ndp[i][true] will store the maximum cost up to index i considering nums[i] as positive.\ndp[i][false] will store the maximum cost up to index i considering nums[i] as negative.\n\n**Recursive Function with Memoization:**Define a recursive function solve(nums, i, check, dp) that computes the maximum cost from index i onwards with the current sign indicated by check.\n**Base Case:** If i exceeds the array bounds, return 0.\n**Memoization: **If the result is already computed, return it.\n**Compute two possible costs:**\nContinue the current subarray.\nStart a new subarray.\nOptimal Solution:\n\nStart from the first element with a positive sign and recursively compute the maximum cost using the solve function.\nReturn the computed maximum cost.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(N) where N is the length of array\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(N) where N is the length of array\n\n# Code\n```\nclass Solution {\npublic:\n    long long int solve(vector<int>&nums,int i,bool check,vector<vector<long long int>> & dp){\n        if(i>=nums.size()) return 0;\n        if(dp[i][check]!=-1) return dp[i][check];\n        long long int part= solve(nums,i+1,true,dp)+ (check ? nums[i]: -1*nums[i]);\n        long long int select= solve(nums,i+1,!check,dp)+ (check? nums[i]: -1*nums[i]);\n        return dp[i][check]=max(part,select);\n    }\n    long long maximumTotalCost(vector<int>& nums) {\n        vector<vector<long long int>> dp(nums.size(),vector<long long int >(2,-1));\n        return solve(nums,0,true,dp);\n    }\n};\n```
['C++']