Solution shown below is according to Book - Introduction to Algorithms, which originally uses divide and conquer to solve this problem and offers an idea towards linear time algorithm.

```
int maxSubArray(vector<int>& nums) {
int rst = INT_MIN;
int preMax = INT_MIN;
for (int i = 0; i < nums.size(); ++i) {
int curMax = (preMax <= 0) ? nums[i] : nums[i]+preMax;
rst = max(rst, curMax);
preMax = curMax;
}
return rst;
}
```