Dynamic Programming || Easy Approach with intuition || Memoization || C++
Intuition\nFor each element in the array, we have two possibilities:\n\n1. Start a new subarray from the current element.\n2. Continue the current subarray by a
# Intuition\nFor each element in the array, we have two possibilities:\n\n1. Start a new subarray from the current element.\n2. Continue the current subarray by adding the current element.\n\nWe use a dynamic programming approach to keep track of these possibilities and make optimal decisions at each step.\n\n# Approach\n1. Recursive Function: We define a recursive function fun(ind, start, sign) that returns the maximum possible sum considering the following parameters:\n\n(i) ind: The current index in the nums array.\n(ii) start: A flag indicating whether we are starting fresh (0) or continuing (1).\n(iii) sign: A flag indicating the current sign of the next operation (1 for adding the element, 0 for subtracting).\n\n2. Base Case: If ind equals the size of nums, we return 0 because we\'ve processed all elements.\n\n3. Memoization: We use a 3D vector dp to store the results of subproblems to avoid redundant calculations.\n\n4. Recursive Cases:\n- If start is 0, we must start a new subarray with the current element.\n- If start is 1, we consider both adding and not adding the current element, depending on the sign.\n- If sign is 1, we subtract the current element.\n- If sign is 0, we add the current element.\n\n5. Return Value: The function maximumTotalCost initializes the dp array and starts the recursion from the first element with both start and sign set to 0.\n\n# Complexity\n- Time complexity:\nThe total number of unique states is n * 2 * 2 = 4n. Each state is computed in constant time \uD835\uDC42(1), so the overall time complexity is O(n).\n\n- Space complexity:\n The dp array requires O(n) space and the recursion stack space also uses O(n), so the overall space complexity is O(n).\n\n\n# Code\n```\nclass Solution {\npublic:\n    long long fun(int ind, int start,int sign,vector<vector<vector<long long>>>&dp, vector<int>&nums)\n    {\n        if(ind == nums.size()) return 0;\n        if(dp[ind][start][sign] != -1e13) return dp[ind][start][sign];\n        long long ans = -1e13;\n        if(start == 0)  //means fresh start we need to take the current element\n        {\n          ans = max(ans,nums[ind]+fun(ind+1,1,1,dp,nums));\n        }\n        else  //not a fresh start, we are continuing 2 cases either we continue or not means either we take or not take\n        {\n            if(sign == 1)   //minus sign\n            {\n            ans = max(ans,-nums[ind]+fun(ind+1,1,0,dp,nums)); //take\n            ans = max(ans,fun(ind,0,0,dp,nums));  //we are not taking that element in continuity and will start fresh from that element\n            }\n            else\n            {\n                ans = max(ans,nums[ind]+fun(ind+1,1,1,dp,nums));\n                ans = max(ans,fun(ind,0,0,dp,nums));\n            }\n        }\n        return dp[ind][start][sign] = ans;\n    }\n    long long maximumTotalCost(vector<int>& nums) {\n        int n = nums.size();\n        vector<vector<vector<long long>>>dp(n,vector<vector<long long>>(2,vector<long long>(2,-1e13)));\n        return fun(0,0,0,dp,nums);\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C++']