C++ | | Easy Solution | | Top-Down DP | | With Explanation
Approach\nAt each i, we have 2 options:\n Just take nums[i] in the subarray.\n Take nums[i] and nums[i+1] in the subarray\n\ndp[i]: Maximum sum of subarrays fro
# Approach\nAt each `i`, we have 2 options:\n* Just take `nums[i]` in the subarray.\n* Take `nums[i]` and `nums[i+1]` in the subarray\n\n`dp[i]`: Maximum sum of subarrays from `i` to `n-1`.\n\nBe sure to check for bounds in case of `i+1`\n\n# Complexity\n- Time complexity: $O(n)$\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> nums;\n    long long helper(int i, vector<long long>& dp){\n        if(i >= nums.size()) return 0;\n        \n        if(dp[i] != -1) return dp[i];\n        \n        long long a, b=0;\n        a= nums[i] + helper(i+1, dp);\n        if(i+1 < nums.size()){\n            b = nums[i] - nums[i+1] + helper(i+2, dp);\n            return dp[i] = max(a, b);\n        }\n        else return dp[i] = a;\n        \n    }\n    long long maximumTotalCost(vector<int>& nums) {\n        this->nums= nums;\n        vector<long long> dp(nums.size(),-1);\n        return helper(0,dp);\n       \n    }\n};\n```
['C++']