[Java] DP solution with at most K deletions
You can extend the maximum subarray problem here to find a subarray with maximum sum after atmost k deletions.\nFor any given ith element with k deletions remai
You can extend the maximum subarray problem here to find a subarray with maximum sum after atmost k deletions.\nFor any given ith element with k deletions remaining, if ith element is a part of the solution you would have two options to choose from to form the solution:-\n1. Don\'t choose the ith element, hence k would decrease by 1 => f(i-1,k-1)\n2. Choose the ith element => f(i-1,k)+a[i]\n\nf(i,k) = Math.max(f(i-1,k-1),f(i-1,k)+a[i]);\n\nclass Solution {\n    public int maximumSum(int[] a) {\n        if(a == null) return 0;\n        \n        int n = a.length;\n        int K=1;\n        if(n == 0){return 0;}\n        \n        int[][] dp = new int[n+1][K+1];\n        for(int i=0;i<=K;i++){\n            dp[0][i] = Integer.MIN_VALUE;\n        }\n        \n        int answer = Integer.MIN_VALUE;\n        for(int i=1;i<=n;i++){\n            for(int k=0;k<=K;k++){\n                if(dp[i-1][k] >= 0){\n                    dp[i][k] = Math.max((k-1>=0 ? dp[i-1][k-1] : Integer.MIN_VALUE), dp[i-1][k]+a[i-1]);\n                }else{\n                    dp[i][k] = a[i-1];\n                }\n                answer=Math.max(answer,dp[i][k]);\n            }\n        }\n        return answer;\n    }\n}
['Dynamic Programming']