Two Approaches - Recursive and Dynamic Programming Solutions
Intuition\nThe problem is similar to jump by 1 step and jump by 2 step, whereas in this case, we are referring it to select the subarray of length 1 or of lengt
# Intuition\nThe problem is similar to jump by 1 step and jump by 2 step, whereas in this case, we are referring it to select the subarray of length 1 or of length 2.\n\n# Complexity\nBetter complexity when DP array is used over recursion, to pre solve the subproblems in recursion.\n\n# Tip\nBoth the solutions are given in the single code itself, if recursive approach is required, just remove dp from everywhere, else everything is for dp.\n\n# Code\n```\nclass Solution {\nprivate:\n    long long func(int index, vector <int> &nums, vector <long long> &dp) {\n        if (index == nums.size()) return 0;\n        if (index == nums.size()-1) return nums[index] + func(index+1, nums, dp);\n\n        if (dp[index] != -1) return dp[index];\n\n        long long jump_1 = nums[index] + func(index+1, nums, dp);\n        long long jump_2 = nums[index] - nums[index+1] + func(index+2, nums, dp);\n        return dp[index] = max(jump_1, jump_2);\n    }\npublic:\n    long long maximumTotalCost(vector<int>& nums) {\n        long long ans = 0;\n        int n = nums.size();\n        if (n==1) return nums[0];\n        vector <long long> dp(n+1, -1);\n        return func(0, nums, dp);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'C++']