Simple DP Similar to Take/Not-take✅
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    long partition(int ar[], int i, long dp[][],int prev){\n        if(i<0) return 0;\n        if(i==0){\n            if(prev==0) return ar[0];\n            else return Integer.MIN_VALUE;\n        }\n        if(dp[i][prev]!=-1) return dp[i][prev];\n        long ans = Integer.MIN_VALUE;\n        if(prev==0){\n            ans = Math.max(ans,ar[i] + partition(ar,i-1,dp,0));\n            ans = Math.max(ans,ar[i] + partition(ar,i-1,dp,1));\n        }\n        else{\n            ans = Math.max(ans, -ar[i] + partition(ar,i-1,dp,0));\n        }\n        return dp[i][prev] = ans;\n    }\n    public long maximumTotalCost(int[] nums) {\n        int n = nums.length;\n        long dp[][] = new long[n][2];\n        for(int i=0;i<n;i++) Arrays.fill(dp[i],-1);\n        long lf = partition(nums,n-1,dp,0);\n        long rf = partition(nums,n-1,dp,1);\n        return Math.max(lf,rf);\n    }\n}\n```
['Array', 'Dynamic Programming', 'Memoization', 'C++', 'Java']