maximal subarray sum For atmost k deletions 2d dp
Code\n\nclass Solution {\npublic:\n    int maximumSum(vector<int>& arr) {\n        \n        int n=arr.size(),k=1;\n        int dp[n][k+1];\n\n    // dp[i][j] -
# Code\n```\nclass Solution {\npublic:\n    int maximumSum(vector<int>& arr) {\n        \n        int n=arr.size(),k=1;\n        int dp[n][k+1];\n\n    // dp[i][j] -> maximal subarray sum for all subarrays ending at index i with exactly j deletions\n    // dp[i][j] -> max(dp[i-1][j]+arr[i],dp[i-1][j-1]);\n// 1st option is including the ith index in subarray and not deleting it\n// 2nd option is also  including the ith index(because dp[i][j] should end at index i ) in subarray but deleting it from subarray  \n\n    dp[0][0]=arr[0];\n    for(int i=1;i<n;i++)\n    {\n        dp[i][0]=max(dp[i-1][0]+arr[i],arr[i]);\n    }\n\n    for(int j=1;j<=k;j++)\n    {\n        for(int i=0;i<n;i++)\n        {\n            if(j>=i+1) // no of deletions greater or equal to no of elements in subarray\n            {\n                dp[i][j]=0;\n            }\n            else\n                dp[i][j]=max(dp[i-1][j]+arr[i],(j?dp[i-1][j-1]:INT_MIN));\n        }\n    }\n    int ans=INT_MIN;\n    for(int j=0;j<=k;j++)\n    {\n        for(int i=0;i<n;i++){\n            //cout<<dp[i][j]<<" ";\n            if(j<i+1)\n            {\n                ans=max(ans,dp[i][j]);\n            }\n        }\n        //cout<<endl;\n    }\n    return ans;      \n\n\n    }\n};\n```\n\n# Sample Test cases for k deletions\n\n5 3\n-1 2 -3 5 4\n\n11\n\n5 5\n1 2 3 4 5\n\n15\n\n5 5\n-1 -2 -3 -4 -5\n\n-1\n\n4 1\n1 -2 0 3\n\n4\n\n4 1\n1 -2 -2 3\n\n3\n\n10 0\n6 -5 3 -7 6 -1 10 -8 -8 8\n\n15\n\n10 2\n6 -5 3 -7 6 -1 10 -8 -8 8\n\n24\n\n10 6\n6 -5 3 -7 6 -1 10 -8 -8 8\n\n33\n\n7 1\n-2 1 3 -2 4 -7 20\n\n26\n\n6 2\n-1 1 -1 -1 1 1\n\n3\n\n
['C++']