Find the Greatest Contiguous Segment Sum
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Find the greatest possible sum of a nonempty contiguous subarray of the integer array `nums`. Return that sum, not the subarray or its endpoints.
```cpp
int maxSubArray(vector<int>& nums);
```
### Examples
```text
Input: nums = [-5,2,3,-1,2,-8]
Output: 6
```
The contiguous segment `[2,3,-1,2]` has sum 6.
```text
Input: nums = [-7,-2,-9]
Output: -2
```
An empty subarray is not an alternative to the best single negative entry.
### Constraints
- `1 <= nums.length <= 100000`.
- Each entry is between -10000 and 10000, inclusive.
### Source follow-up
After obtaining a linear-time method, also develop a divide-and-conquer solution.
Overview: Find the largest nonempty contiguous-subarray sum, including all-negative inputs and a divide-and-conquer follow-up.
