We can observe that for each `i`

best solution (maximum sum) for segment ending at `i`

will be `sum([0, i]) - min(sum([0, j]))`

for `j < i`

, also `sum([j, i]) = sum([0, i]) - sum([0, j - 1])`

, i.e. to find biggest sum of segment ending at `i`

we need to subtract minimal (sum-wise) segment `[0, j]`

, `j < i`

. Then we need just to compute maximum out of all `i`

-ending segments.

Time Complexity: O(N)

Space Complexity: O(1)

```
#include <algorithm>
using namespace std;
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.empty()) return 0;
int begin_sum = 0, min_begin_sum = 0, max_interval_sum = nums[0];
for (int i = 0; i < nums.size(); ++i) {
begin_sum += nums[i];
max_interval_sum = max(max_interval_sum, begin_sum - min_begin_sum);
min_begin_sum = min(min_begin_sum, begin_sum);
}
return max_interval_sum;
}
};
```