Simple DP Approach || Memorization || Java || C++ || Python
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need to consider only subarrays of size 1 and 2 to maximize the cost.\n\n\n\n\n\n\n\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need to consider only subarrays of size 1 and 2 to maximize the cost.\n\n\n\n\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe proposed solution uses a dynamic programming approach with space optimization. Instead of maintaining an entire DP array, it uses two variables (secondPrev and firstPrev) to keep track of the maximum costs at previous states. This is more efficient in terms of space complexity. Let\'s go through the solution step-by-step:\n\nBase Case:\nIf there is only one element in nums, the maximum total cost is the element itself.\n\nInitial Values:\n\nsecondPrev holds the maximum cost for the subarray ending two indices before the current index.\nfirstPrev holds the maximum cost for the subarray ending at the previous index.\nInitially, secondPrev is set to the first element (nums[0]), as the subarray consisting of the first element only has that cost.\nfirstPrev is set to the maximum of two possible subarrays: [nums[0], nums[1]] or [nums[0], -nums[1]], which corresponds to nums[0] + nums[1] or nums[0] - nums[1].\nIterate Through the Array:\n\nFor each element starting from the third one (index 2), calculate the maximum cost considering extending the subarray from two indices back or extending the subarray from one index back.\nUpdate secondPrev and firstPrev for the next iteration.\nReturn Result:\n\nAfter processing all elements, firstPrev will contain the maximum total cost.\n\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n\n# Java Code\n```\nclass Solution {\n    public long maximumTotalCost(int[] nums) {\n        if (nums.length == 1) {\n            return nums[0];\n        }\n        \n        // Initial values for the dynamic programming approach\n        long secondPrev = nums[0];\n        long firstPrev = Math.max((long) nums[0] + nums[1], (long) nums[0] - nums[1]);\n        \n        for (int i = 2; i < nums.length; i++) {\n            // Calculate the maximum cost for the subarray ending at the current index\n            long current = Math.max(secondPrev + nums[i - 1] - nums[i], firstPrev + nums[i]);\n            // Update the previous values for the next iteration\n            secondPrev = firstPrev;\n            firstPrev = current;\n        }\n        \n        return firstPrev;\n    }\n}\n```\n# Python Code\n```\nclass Solution:\n    def maximumTotalCost(self, nums: List[int]) -> int:\n        # If there is only one element in the list then the maximum total cost will be the element itself \n        if len(nums) == 1:\n            return nums[0]\n        \n        # Initial values for the dynamic programming approach\n        secondPrev = nums[0]\n        firstPrev = max(nums[0] + nums[1], nums[0] - nums[1])\n        \n        for i in range(2, len(nums)):\n            # Calculate the maximum cost for the subarray ending at the current index\n            current = max(secondPrev + nums[i-1] - nums[i], firstPrev + nums[i])\n            # Update the previous values for the next iteration\n            secondPrev = firstPrev\n            firstPrev = current\n            \n        return firstPrev\n```\n# C++ Code\n```\nclass Solution {\npublic:\n    long long maximumTotalCost(vector<int>& nums) {\n         \n        if (nums.size() == 1) {\n            return nums[0];\n        }\n        \n        // Initial values for the dynamic programming approach\n        long long secondPrev = nums[0];\n        long long firstPrev = std::max((long long)nums[0] + nums[1], (long long)nums[0] - nums[1]);\n        \n        for (size_t i = 2; i < nums.size(); i++) {\n            // Calculate the maximum cost for the subarray ending at the current index\n            long long current = std::max(secondPrev + nums[i - 1] - nums[i], firstPrev + nums[i]);\n            // Update the previous values for the next iteration\n            secondPrev = firstPrev;\n            firstPrev = current;\n        }\n        \n        return firstPrev;\n    }\n};\n```\n\n\n
['Dynamic Programming', 'Memoization', 'C++', 'Java', 'Python3']