C++ Very Easy to Understand Solution (DP and Constant Space)
This question is asking us to find the maximum sum subarray by deleting exactly one element from it.\n\nAt each ith element, We have two choices, delete the pre
This question is asking us to find the maximum sum subarray by deleting exactly one element from it.\n\nAt each ith element, We have two choices, delete the present element or include the sum in our subarray.\n\nWhen input is of size 1\nBase Case :  \nmaximum sum subarray of 1 element without deletng the element is element itself\nmaximum sum subarray of 1 element when you are deleting the element is take any number like 1e6.\n\nNow we know there are 2 states in our dp.\n**dp(i, 0) -> maximum sum subarray at the ith index, when you have not used the deletion yet. \ndp(i, 1)    -> maximum sum subarray at the ith index when you have already used the one deletion or you can delete present element and include previous sum**\n\n\ndp[i][0] = max(arr[i], arr[i] + dp[i - 1][0]);\ndp[i][1]= max( dp[i - 1][1] + arr[i], dp[i - 1][0]);\n\n* Dp Approach \nTime Complexity : O(N) Space Complexity : O(N)\n```\nclass Solution {\npublic:\n    int maximumSum(vector<int>& arr) {\n        \n      int n = arr.size();\n      int dp[n][2];\n      int ans = INT_MIN;\n      \n      dp[0][0] = arr[0];\n      dp[0][1] = -1e6;\n      \n      for(int i = 1; i < n; i++) {\n        \n//dp(i, 0) means that maximum sum subarray at ith index with no deletion.\n        dp[i][0] = max( arr[i], dp[i - 1][0] + arr[i] );\n\n// //dp(i, 1) means that maximum sum subarray at ith index with 1 deletion.\n//         dp[i][1] = max(previous sum with deletion  + include present element, delete present element and include previous sum withno deletion );\n        \n        dp[i][1] = max( dp[i - 1][1] + arr[i], dp[i - 1][0]);\n      }\n      \n      for(int i = 0; i < n; i++)\n        ans = max(ans, max(dp[i][0], dp[i][1]));\n      \n      return ans;\n    }\n};\n```\n\n\n* Optimised DP with Constatnt Space\nTime Complexity : O(N) Space Complexity : O(1)\n\n```\nclass Solution {\npublic:\n    int maximumSum(vector<int>& arr) {\n        \n      int n = arr.size();\n      int ans = INT_MIN;\n      \n      int prevSumWithNoDeletion = arr[0];\n      int prevSumWithOneDeletion = -1e6;\n      \n      ans = max(ans, max(prevSumWithNoDeletion, prevSumWithOneDeletion ));\n      \n      for(int i = 1; i < n; i++)\n      {\n        int presentSumWithNoDeletion = max( arr[i], prevSumWithNoDeletion + arr[i] );\n        int presentSumWithOneDeletion = max(prevSumWithOneDeletion + arr[i], prevSumWithNoDeletion );\n        \n        prevSumWithNoDeletion = presentSumWithNoDeletion;\n        prevSumWithOneDeletion = presentSumWithOneDeletion;\n        \n        ans = max(ans, max(presentSumWithNoDeletion, presentSumWithOneDeletion ));\n      }\n      return ans;\n    }\n};\n```
[]