Recursion  + Memoization General approach for K deletions C++
\nclass Solution {\npublic:\n    // Choices that we\'ve:-\n    // 1. Don\'t delete the current Element and find the maximum sum\n    //2. Delete the current ele
```\nclass Solution {\npublic:\n    // Choices that we\'ve:-\n    // 1. Don\'t delete the current Element and find the maximum sum\n    //2. Delete the current element and find the maximum sum\n    int ans;\n    int solve(vector<int>&arr,int dp[][2],int i,int k)\n    {\n        if(i==0)\n            return arr[i]; // If only One element Left in the array we need to return it as the subarray can\'t be empty\n        if(dp[i][k]!=-1) // Memoization\n            return dp[i][k];\n        dp[i][k] = max(arr[i],arr[i] + solve(arr,dp,i-1,k)); //  Do not Delete the current Element\n        if(k) // If there\'s any deletion left\n            dp[i][k] = max(dp[i][k],solve(arr,dp,i-1,k-1));\n        ans = max(ans,dp[i][k]); // Store the maximum sum\n        return dp[i][k];\n    }\n    int maximumSum(vector<int>& arr) {\n        int n = arr.size();\n        ans = arr[0];\n        int dp[n][2]; //  dp[i][j] = maximum subarray sum ending at i with j deletions\n        memset(dp,-1,sizeof(dp));\n        solve(arr,dp,n-1,1);\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C']