| Simple 5 line | Kadane's Algorithm | Beats 91%, 82% |
Intuition\nSimple solution using the idea of Kadane\'s Algorithm. This solution is built on top of 53. Maximum Subarray question\'s solution using Kadane\'s Alg
# Intuition\nSimple solution using the idea of Kadane\'s Algorithm. This solution is built on top of [53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/) question\'s solution using Kadane\'s Algorithm. \n \n---\n\n# Approach\nThe basic idea of Kadane\'s algorithm for solving Maximum Subarray problem is a greedy like approach where we keep track of 2 variables: \n- `cur_sum`: *sum of current subarray*\n- `max_sum`: *max sum of subarray seen so far*\n\nSolution looks like this: \n\n```\nclass Solution:\n    def maxSubArray(self, nums: List[int]) -> int:\n        #1\n        cur_sum = max_sum = nums[0]\n        #2\n        for num in nums[1:]:\n            #3\n            cur_sum = max(cur_sum + num, num)\n            #4\n            max_sum = max(max_sum, cur_sum)\n        #5\n        return max_sum\n```\n`#1`: Set `cur_sum` and `max_sum` to first element\n\n`#2`: Iterate over rest of the array\n\n`#3`: \n\n`cur_sum` needs to be set to maximum of 2 things: \n    - `cur_sum + num`: Extend current subarray by adding `num`\n    - `num`: Start a new subarray from `num`\n    \n`#4`: Update `max_sum` to keep track of maximum sum of subarray seen so far\n\n`#5`: Return `max_sum`\n\n\n---\n\nThis question goes a step further on Maximum Subarray one, where we are allowed to delete one of the elements in the array. We can easily extend the previous solution to take care of the deletion case.\n\nNow we need to keep track of 3 variables:\n- `cur_sum_del`: *sum of current subarray with **one** deletion*\n- `cur_sum_no_del`: *sum of current subarray with **no** deletion*\n- `max_sum`: *max sum of subarray seen so far*\n\nSolution looks like this:\n```\nclass Solution:\n    def maximumSum(self, arr: List[int]) -> int:\n        #1\n        cur_sum_no_del = cur_sum_del = max_sum = arr[0]\n        #2 \n        for num in arr[1:]:\n            #3\n            cur_sum_del = max(cur_sum_del + num, num, cur_sum_no_del)\n            #4\n            cur_sum_no_del = max(cur_sum_no_del + num, num)\n            #5\n            max_sum = max(max_sum, cur_sum_no_del, cur_sum_del)\n        #6\n        return max_sum\n```\n\n`#1`: Set `cur_sum_del`, `cur_sum_no_del` and `max_sum` to first element\n\n`#2`: Iterate over rest of the array\n\n`#3`: \n    \n`cur_sum_del` needs to be set to maximum of 3 things\n    - `cur_sum_del + num`: Extend current subarray with one deletion by adding `num`\n    - `cur_sum_no_del`: Delete the current `num` \n    - `num`: Start a new subarray from `num`\n\n`#4`: \n\n`cur_sum_no_del` needs to be set to maximum of 2 things:\n    - `cur_sum_no_del + num`: Extend current subarray without deletion by adding `num`\n    - `num`: Start a new subarray from `num`\n\n`#5`: Update `max_sum` to keep track of maximum sum of subarray seen so far\n\n`#6`: Return `max_sum`\n\n# Complexity\n- Time complexity:\nO(N)\n\n- Space complexity:\nO(1)\n\n![Screenshot 2023-12-17 at 8.43.34\u202FPM.png](https://assets.leetcode.com/users/images/e46e172c-0b41-4637-a774-03636b9d531e_1702874658.6033685.png)\n
['Python3']