Fully Detailed Solution using Kadane's modification | DP | Beats 100 percent in Time and space
Approach\n\n### Dynamic Programming\nTo solve this problem, we use a dynamic programming approach to keep track of two states at each position in the array:\n1.
## Approach\n\n### Dynamic Programming\nTo solve this problem, we use a dynamic programming approach to keep track of two states at each position in the array:\n1. **`prevDeleted`**: Maximum subarray sum ending at the current index, where one deletion has already been used.\n2. **`prevNotDeleted`**: Maximum subarray sum ending at the current index, without any deletions.\n\n### Steps\n1. Initialize:\n   - `prevDeleted = 0` - Represents the maximum sum with one deletion used.\n   - `prevNotDeleted = arr[0]` - Represents the maximum sum without deletion, initialized with the first element of `arr`.\n   - `maxi = arr[0]` - To store the global maximum sum across both states.\n\n2. Iterate through the array from the second element:\n   - Update `prevDeleted` by choosing the maximum between extending the previous deleted sum (`prevDeleted + arr[i]`) and starting fresh with the previous non-deleted sum (`prevNotDeleted`).\n   - Update `prevNotDeleted` by choosing the maximum between extending the previous non-deleted sum (`prevNotDeleted + arr[i]`) and starting a new sum from the current element (`arr[i]`).\n   - Update `maxi` with the highest value of `prevDeleted`, `prevNotDeleted`, and `maxi`.\n\n3. Return `maxi` as the result.\n\n### Complexity Analysis\n- **Time Complexity**: O(n), where n is the number of elements in `arr`. We only iterate through the array once.\n- **Space Complexity**: O(1), as we only use a constant amount of extra space for variables.\n\n## Code\n\n```cpp\nclass Solution {\npublic:\n    int maximumSum(vector<int>& arr) {\n        int prevDeleted = 0;\n        int prevNotDeleted = arr[0];\n        int maxi = arr[0];\n        \n        for(int i = 1; i < arr.size(); i++) {\n            prevDeleted = max(prevDeleted + arr[i], prevNotDeleted);\n            prevNotDeleted = max(prevNotDeleted + arr[i], arr[i]);\n            maxi = max({prevDeleted, prevNotDeleted, maxi});\n        }\n        \n        return maxi;\n    }\n};\n```\n\n## Example\n```cpp\nInput: arr = [1, -2, 0, 3]\nOutput: 4\nExplanation: Deleting -2 gives [1, 0, 3] with a maximum sum of 4.\n```\n\n## Edge Cases\n- **All Negative Elements**: If `arr` contains only negative elements, deleting the minimum negative element should yield the maximum possible sum.\n- **Single Element**: If `arr` has only one element, the output will be the value of that element itself (as there\u2019s no element to delete).\n
['Array', 'Dynamic Programming', 'C++']