C++ O(n), 2 cases of Maximum Subarray
Intuition\nWe can use 53. Maximum Subarray as our starting point. The idea there is to split our array into subarrays with positive balance. In other words, whe
# Intuition\nWe can use [53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/) as our starting point. The idea there is to split our array into subarrays with positive balance. In other words, when our running sum falls below zero, we start a new subarray. \n\nHowever, here we can have two cases:\n1. Removed element increases the sum of a subarray:\n\t- Example: `[6, -5, -5, 5, -4, 5]`, =>`10` (`[5, -4, 5]`, removed `-4`).\n2. Removed element joins two subarrays.\n\t- Example: `[1, -2, 0, 3]` => `4` (entire array, removed `-2`).\n\nQ: Why do we need two cases?\nA: If you look at the first example - `[6, -5, -5, 5, -4, 5]` - and apply the second strategy, the result would be `7`. The entire array is included, and we removed `-5`. \n\nQ: Why we reset `i` in the second case?\nA: Look at this example: `[1,-200,2,-200,3]`. We first find `[1, -200, 2]` with the sum `3` (removed `-200`). We now need to analyze another subarray start start with `2`: `[2, -200, 3]` wiht the sum `5`. To do that, we need to reset `i` to point to the element after the previous minimum one.\n# Solution\nWe basically run the classic maximum subarray algorithm twice. For case 1, we track the minimum negative element for each subarray and subtract it from the running sum.\n\nFor case 2, we also track the minimum element but use it to detect whether we need to start a new subarray.\n```\nint maximumSum(vector<int>& nums) {\n  int run1 = 0, min1 = 0, run2 = 0, min2 = 0, res = INT_MIN;\n  for (int n : nums)\n  {\n      if (run1 <= 0)\n          run1 = min1 = 0;\n      run1 += n;\n      res = max(res, run1 - min1);\n      min1 = min(min1, n);\n  }\n  for (int i = 0, min_i = -1; i < nums.size(); ++i) {\n      if (run2 - min2 <= 0) {\n          run2 = min2 = 0;\n          if (min_i != -1) {\n              i = min_i;\n              min_i = -1;\n              continue;\n          }\n      }\n      run2 += nums[i];\n      res = max(res, run2 - min2);\n      if (nums[i] < min2) {\n          min_i = i;\n          min2 = nums[i];\n      }\n  }\n  return res;\n}\n```\n## Complexity Analysis\n- Runtime: O(n)\n- Memory: O(1)\n
[]