✅✅ Detailed explanation || Recursive, Memoized Solution 😱😃
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires splitting the array into subarrays to maximize the total cost, whe
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires splitting the array into subarrays to maximize the total cost, where the cost of each subarray alternates between adding and subtracting elements. We use a recursive approach with memoization to solve this efficiently.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nRecursive Function with Memoization:\n\nThe solve function is a recursive function with memoization to avoid recalculating results for the same state multiple times.\n\nIt has two parameters: the current index idx and a boolean pos which indicates whether the current state is positive or negative.\n\nDP Table:\n\nThe DP table dp is a 2D array where dp[idx][0] and dp[idx][1] store the maximum cost starting from index idx with pos being false or true, respectively.\n\nBase Case:\n\nWhen idx is out of bounds (idx >= n), the function returns 0.\n\nMemoization Check:\n\nBefore performing any calculations, the function checks if the result is already computed and stored in dp[idx][pos].\n\nState Transition:\n\nNote -> pos indicates whether the current value should be multiplied by -1.\n\npos = true means the current value should not be multiplied by -1.\n\npos = false means the current value should be multiplied by -1.\n\nIf pos is true, it adds nums[idx] to the result and calls solve for the next index with pos being false.\n\nIf pos is false, it computes two potential results: taking the current element with a negative sign and moving to the next element with pos being true, or not taking the current element and moving to the next element with pos being false. \n\nThe maximum of these two results is stored in dp[idx][pos].\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe DP table has dimensions [n][2], where n is the size of the input array nums.\n\nThe function solve is called at most 2 * n times, each taking \nconstant time O(1) for memoization checks and state transitions.\n\nHence, the overall time complexity is O(n).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity includes the DP table and the recursion stack.\n\nThe DP table dp requires O(2 * n) = O(n) space.\n\nThe recursion stack can go up to a maximum depth of n, requiring O(n) space.\n\nTherefore, the total space complexity is O(n).\n\n# Code\n```C++ []\n\nclass Solution {\npublic:\n    \n    int n;\n    long long dp[100004][2];\n    \n    long long solve(vector<int>& nums, int idx, bool pos) {\n        \n        if(idx >= n) return 0;\n        \n        if(dp[idx][pos] != -1) return dp[idx][pos];\n        \n        if(pos) {\n              dp[idx][pos] =  nums[idx] + solve(nums, idx+1, false);\n        }\n        else {\n            long long take = solve(nums, idx+1, true)-nums[idx];\n            long long not_take = solve(nums, idx+1, false)+nums[idx];\n            dp[idx][pos] = max(take, not_take);\n        }\n        \n        return dp[idx][pos];\n    }\n    \n    long long maximumTotalCost(vector<int>& nums) {\n        \n        n = nums.size();\n        \n        memset(dp, -1, sizeof(dp));\n        \n        return solve(nums, 0, true);\n    }\n};\n```\n```python []\nclass Solution:\n    def maximumTotalCost(self, nums: List[int]) -> int:\n        n = len(nums)\n        dp = [[-1, -1] for _ in range(n)]\n\n        def solve(idx: int, pos: bool) -> int:\n            if idx >= n:\n                return 0\n\n            if dp[idx][pos] != -1:\n                return dp[idx][pos]\n\n            if pos:\n                dp[idx][pos] = nums[idx] + solve(idx + 1, False)\n            else:\n                take = solve(idx + 1, True) - nums[idx]\n                not_take = solve(idx + 1, False) + nums[idx]\n                dp[idx][pos] = max(take, not_take)\n\n            return dp[idx][pos]\n\n        return solve(0, True)\n\n\n```\n```java []\nimport java.util.Arrays;\n\nclass Solution {\n    private int n;\n    private long[][] dp;\n\n    private long solve(int[] nums, int idx, boolean pos) {\n        if (idx >= n) return 0;\n\n        if (dp[idx][pos ? 1 : 0] != -1) return dp[idx][pos ? 1 : 0];\n\n        if (pos) {\n            dp[idx][1] = nums[idx] + solve(nums, idx + 1, false);\n            return dp[idx][1];\n        } else {\n            long take = solve(nums, idx + 1, true) - nums[idx];\n            long notTake = solve(nums, idx + 1, false) + nums[idx];\n            dp[idx][0] = Math.max(take, notTake);\n            return dp[idx][0];\n        }\n    }\n\n    public long maximumTotalCost(int[] nums) {\n        n = nums.length;\n        dp = new long[n][2];\n        for (int i = 0; i < n; i++) {\n            Arrays.fill(dp[i], -1);\n        }\n        return solve(nums, 0, true);\n    }\n\n    public static void main(String[] args) {\n        Solution sol = new Solution();\n        int[] nums = {1, 2, 3, 4, 5};\n        System.out.println(sol.maximumTotalCost(nums)); \n    }\n}\n\n```\n
['Memoization', 'C++', 'Java', 'Python3']