✔️ Beats 100% : 1D -DP : Detailed Step-by-Step Explanation - C++/Java/Python/C#/JS/Ruby/Go/Dart
Intuition\nWe need to find the maximum cost of a subarray where the cost is calculated by flipping the sign of every second element. This means alternating sign
# Intuition\nWe need to find the maximum cost of a subarray where the cost is calculated by flipping the sign of every second element. This means alternating signs as we move through the array. Dynamic Programming (DP) is suitable to solve this problem efficiently.\n\n# Approach\n1. **Dynamic Programming Table:** Use a 2D DP table where `dp[i][j]` represents the maximum cost of the subarray starting at index `i`, with `j` indicating whether the previous number included in the cost was positive (`j=1`) or negative (`j=0`).\n\n2. **Recursive Definition:**\n   - If `prevPositive` is true, we add `nums[idx]` to the cost.\n   - If `prevPositive` is false, we subtract `nums[idx]` from the cost.\n\n3. **Base Case:** If we reach the end of the array, the cost is `0`.\n\n4. **Choice Diagram:**\n   - Include the current element in the subarray with appropriate sign change.\n   - Start a new subarray from the current element.\n\n5. **Initialization:** Initialize the DP table with `-1` to indicate uncomputed states.\n\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(n)$$\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    // Memoization table: -1 indicates not computed yet\n    long long dp[100005][2];\n\n    long long maxCost(int idx, bool prevPositive, std::vector<int>& nums) {\n        int n = nums.size();\n        if (idx >= n) return 0;\n\n        if (dp[idx][prevPositive] != -1) {\n            return dp[idx][prevPositive];\n        }\n\n        long long includeCurrent = nums[idx];\n        if (!prevPositive) {\n            includeCurrent = -nums[idx];\n        }\n\n        long long continueSubarray = includeCurrent + maxCost(idx + 1, !prevPositive, nums);\n        long long startNewSubarray = nums[idx] + maxCost(idx + 1, false, nums);\n\n        if (idx == 0) {\n            // If we are at the beginning, we cannot start with a negative sign\n            dp[idx][prevPositive] = startNewSubarray;\n        } else {\n            dp[idx][prevPositive] = std::max(continueSubarray, startNewSubarray);\n        }\n\n        return dp[idx][prevPositive];\n    }\n\n    long long maximumTotalCost(std::vector<int>& nums) {\n        std::memset(dp, -1, sizeof(dp));\n        return maxCost(0, true, nums);\n    }\n};\n```\n```python []\nclass Solution:\n    def __init__(self):\n        self.dp = {}\n\n    def maxCost(self, idx, prevPositive, nums):\n        if idx >= len(nums):\n            return 0\n\n        if (idx, prevPositive) in self.dp:\n            return self.dp[(idx, prevPositive)]\n\n        includeCurrent = nums[idx] if prevPositive else -nums[idx]\n\n        continueSubarray = includeCurrent + self.maxCost(idx + 1, not prevPositive, nums)\n        startNewSubarray = nums[idx] + self.maxCost(idx + 1, False, nums)\n\n        if idx == 0:\n            self.dp[(idx, prevPositive)] = startNewSubarray\n        else:\n            self.dp[(idx, prevPositive)] = max(continueSubarray, startNewSubarray)\n\n        return self.dp[(idx, prevPositive)]\n\n    def maximumTotalCost(self, nums):\n        self.dp.clear()\n        return self.maxCost(0, True, nums)\n\n```\n```C# []\npublic class Solution {\n    private long[,] dp;\n\n    private long MaxCost(int idx, bool prevPositive, List<int> nums) {\n        int n = nums.Count;\n        if (idx >= n) return 0;\n\n        if (dp[idx, prevPositive ? 1 : 0] != -1) {\n            return dp[idx, prevPositive ? 1 : 0];\n        }\n\n        long includeCurrent = nums[idx];\n        if (!prevPositive) {\n            includeCurrent = -nums[idx];\n        }\n\n        long continueSubarray = includeCurrent + MaxCost(idx + 1, !prevPositive, nums);\n        long startNewSubarray = nums[idx] + MaxCost(idx + 1, false, nums);\n\n        if (idx == 0) {\n            dp[idx, prevPositive ? 1 : 0] = startNewSubarray;\n        } else {\n            dp[idx, prevPositive ? 1 : 0] = Math.Max(continueSubarray, startNewSubarray);\n        }\n\n        return dp[idx, prevPositive ? 1 : 0];\n    }\n\n    public long MaximumTotalCost(List<int> nums) {\n        dp = new long[nums.Count + 1, 2];\n        for (int i = 0; i <= nums.Count; i++) {\n            dp[i, 0] = dp[i, 1] = -1;\n        }\n        return MaxCost(0, true, nums);\n    }\n}\n\n```\n```Java []\nclass Solution {\n    private long[][] dp;\n\n    private long maxCost(int idx, boolean prevPositive, int[] nums) {\n        int n = nums.length;\n        if (idx >= n) return 0;\n\n        if (dp[idx][prevPositive ? 1 : 0] != -1) {\n            return dp[idx][prevPositive ? 1 : 0];\n        }\n\n        long includeCurrent = nums[idx];\n        if (!prevPositive) {\n            includeCurrent = -nums[idx];\n        }\n\n        long continueSubarray = includeCurrent + maxCost(idx + 1, !prevPositive, nums);\n        long startNewSubarray = nums[idx] + maxCost(idx + 1, false, nums);\n\n        if (idx == 0) {\n            dp[idx][prevPositive ? 1 : 0] = startNewSubarray;\n        } else {\n            dp[idx][prevPositive ? 1 : 0] = Math.max(continueSubarray, startNewSubarray);\n        }\n\n        return dp[idx][prevPositive ? 1 : 0];\n    }\n\n    public long maximumTotalCost(int[] nums) {\n        dp = new long[nums.length + 1][2];\n        for (int i = 0; i <= nums.length; i++) {\n            dp[i][0] = dp[i][1] = -1;\n        }\n        return maxCost(0, true, nums);\n    }\n}\n\n```\n```javascript []\nclass Solution {\n    constructor() {\n        this.dp = {};\n    }\n\n    maxCost(idx, prevPositive, nums) {\n        if (idx >= nums.length) {\n            return 0;\n        }\n\n        const key = `${idx},${prevPositive}`;\n        if (key in this.dp) {\n            return this.dp[key];\n        }\n\n        let includeCurrent = nums[idx];\n        if (!prevPositive) {\n            includeCurrent = -nums[idx];\n        }\n\n        const continueSubarray = includeCurrent + this.maxCost(idx + 1, !prevPositive, nums);\n        const startNewSubarray = nums[idx] + this.maxCost(idx + 1, false, nums);\n\n        if (idx === 0) {\n            this.dp[key] = startNewSubarray;\n        } else {\n            this.dp[key] = Math.max(continueSubarray, startNewSubarray);\n        }\n\n        return this.dp[key];\n    }\n\n    maximumTotalCost(nums) {\n        this.dp = {};\n        return this.maxCost(0, true, nums);\n    }\n}\n\n```\n```Dart []\nclass Solution {\n  Map<String, int> dp = {};\n\n  int maxCost(int idx, bool prevPositive, List<int> nums) {\n    if (idx >= nums.length) {\n      return 0;\n    }\n\n    String key = "$idx,$prevPositive";\n    if (dp.containsKey(key)) {\n      return dp[key]!;\n    }\n\n    int includeCurrent = nums[idx];\n    if (!prevPositive) {\n      includeCurrent = -nums[idx];\n    }\n\n    int continueSubarray = includeCurrent + maxCost(idx + 1, !prevPositive, nums);\n    int startNewSubarray = nums[idx] + maxCost(idx + 1, false, nums);\n\n    if (idx == 0) {\n      dp[key] = startNewSubarray;\n    } else {\n      dp[key] = continueSubarray > startNewSubarray ? continueSubarray : startNewSubarray;\n    }\n\n    return dp[key]!;\n  }\n\n  int maximumTotalCost(List<int> nums) {\n    dp.clear();\n    return maxCost(0, true, nums);\n  }\n}\n\n```\n```ruby []\nclass Solution\n  def initialize\n    @dp = {}\n  end\n\n  def max_cost(idx, prev_positive, nums)\n    return 0 if idx >= nums.length\n\n    key = [idx, prev_positive]\n    return @dp[key] if @dp.key?(key)\n\n    include_current = prev_positive ? nums[idx] : -nums[idx]\n\n    continue_subarray = include_current + max_cost(idx + 1, !prev_positive, nums)\n    start_new_subarray = nums[idx] + max_cost(idx + 1, false, nums)\n\n    if idx == 0\n      @dp[key] = start_new_subarray\n    else\n      @dp[key] = [continue_subarray, start_new_subarray].max\n    end\n\n    @dp[key]\n  end\n\n  def maximum_total_cost(nums)\n    @dp.clear\n    max_cost(0, true, nums)\n  end\nend\n\n \n\n```\n```Go []\npackage main\n\nimport (\n    "fmt"\n    "math"\n)\n\ntype Solution struct {\n    dp map[[2]int64]int64\n}\n\nfunc NewSolution() *Solution {\n    return &Solution{dp: make(map[[2]int64]int64)}\n}\n\nfunc (s *Solution) maxCost(idx int, prevPositive bool, nums []int) int64 {\n    if idx >= len(nums) {\n        return 0\n    }\n\n    key := [2]int64{int64(idx), boolToInt64(prevPositive)}\n    if val, exists := s.dp[key]; exists {\n        return val\n    }\n\n    includeCurrent := int64(nums[idx])\n    if !prevPositive {\n        includeCurrent = -includeCurrent\n    }\n\n    continueSubarray := includeCurrent + s.maxCost(idx+1, !prevPositive, nums)\n    startNewSubarray := int64(nums[idx]) + s.maxCost(idx+1, false, nums)\n\n    if idx == 0 {\n        s.dp[key] = startNewSubarray\n    } else {\n        s.dp[key] = int64(math.Max(float64(continueSubarray), float64(startNewSubarray)))\n    }\n\n    return s.dp[key]\n}\n\nfunc (s *Solution) MaximumTotalCost(nums []int\n\n\n```
['Dynamic Programming', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'C#', 'Dart']