solution.md

# 最大子序和

<p>给定一个整数数组 <code>nums</code> ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。</p><p> </p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>nums = [-2,1,-3,4,-1,2,1,-5,4]<strong><br />输出：</strong>6<strong><br />解释：</strong>连续子数组 [4,-1,2,1] 的和最大，为 6 。</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>nums = [1]<strong><br />输出：</strong>1</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>nums = [0]<strong><br />输出：</strong>0</pre><p><strong>示例 4：</strong></p><pre><strong>输入：</strong>nums = [-1]<strong><br />输出：</strong>-1</pre><p><strong>示例 5：</strong></p><pre><strong>输入：</strong>nums = [-100000]<strong><br />输出：</strong>-100000</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>1 <= nums.length <= 3 * 10<sup>4</sup></code></li>	<li><code>-10<sup>5</sup> <= nums[i] <= 10<sup>5</sup></code></li></ul><p> </p><p><strong>进阶：</strong>如果你已经实现复杂度为 <code>O(n)</code> 的解法，尝试使用更为精妙的 <strong>分治法</strong> 求解。</p>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int res;

    res = sol.maxSubArray(nums);
    cout << res;
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        if (nums.empty())
            return 0;
        int pre = 0, res = nums[0];
        for (auto c : nums)
        {
            pre = max(pre, c);
            res = max(pre, res);
        }
        return res;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        int sum = 0, max_sum = INT_MIN;
        for (int i = 0; i < nums.size(); i++)
        {
            if (sum < 0)
            {
                sum = nums[i];
            }
            else
            {
                sum += nums[i];
            }
            max_sum = max(sum, max_sum);
        }
        return max_sum;
    }
};
```

### B

```cpp
class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        if (nums.size() == 0)
            return NULL;
        return fenzhifa(nums, 0, nums.size() - 1);
    }
    int fenzhifa(vector<int> &nums, int left, int right)
    {
        if (left > right)
            return INT_MIN;
        if (left == right)
            return nums[left];
        int mid = (left + right) / 2;
        int l = fenzhifa(nums, 0, mid - 1);
        int r = fenzhifa(nums, mid + 1, right);
        int t = nums[mid];
        int max_num = nums[mid];
        for (int i = mid - 1; i >= left; i--)
        {
            t += nums[i];
            max_num = max(max_num, t);
        }
        t = max_num;
        for (int i = mid + 1; i <= right; i++)
        {
            t += nums[i];
            max_num = max(max_num, t);
        }
        return max(max(r, l), max_num);
    }
};
```

### C

```cpp
class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        int maxsum = nums[0];
        for (int i = 0; i < nums.size(); i++)
        {
            int sum = 0;
            for (int j = i; j < nums.size(); j++)
            {
                sum = sum + nums[j];
                if (maxsum < sum)
                    maxsum = sum;
            }
        }
        return maxsum;
    }
};
```