dp

    1. class Solution {
    2. public:
    3.    int maxSubArray(vector<int>& nums) {
    4.        int maxsum = nums[0];
    5.        for(int i = 1; i < nums.size(); i++)
    6.        {
    7.            nums[i] = max(nums[i - 1] + nums[i], nums[i]);
    8.            maxsum = max(maxsum, nums[i]);
    9.        }
    10.        return maxsum;
    11.    }
    12. };

    归并的方式

    1. class Solution {
    2.    vector<int> nums;
    3.    int dac(int left, int right)
    4.    {
    5.        if(left == right)
    6.            return nums[left];
    7.        int mid = (left + right)>>1;
    8.        int leftval = dac(left, mid);
    9.        int righval = dac(mid + 1, right);
    10.        int crossleft = -1000000, crossright = -1000000;
    11.        int cur = 0;
    12.        for(int i = mid; i >= left; i--)
    13.        {
    14.            cur += nums[i];
    15.            crossleft = max(crossleft, cur);
    16.        }
    17.        cur = 0;
    18.        for(int i = mid + 1; i <= right; i++)
    19.        {
    20.            cur += nums[i];
    21.            crossright = max(crossright, cur);
    22.        }
    23.        int crossmax = crossleft + crossright;
    24.        return max(max(leftval, righval), crossmax);
    25.    }
    26. public:
    27.    int maxSubArray(vector<int>& _nums) {
    28.        nums = _nums;
    29.        return dac(0, nums.size() - 1);
    30.    }
    31. };

    第二次写题

    3. class Solution {
    4. public:
    5.     int maxSubArray(vector<int>& nums) {
    6.         for(int i = 1; i < nums.size(); i++)
    7.         {
    8.             nums[i] = max(nums[i - 1] + nums[i], nums[i]);
    9.         }
    10.         int res = nums[0];
    11.         for(int i = 1; i < nums.size(); i++)
    12.             res = max(res, nums[i]);
    13.         return res;
    14.     }
    16. };
    1. class Solution {
    2.     int dfs(int start, int end, vector<int> nums)
    3.     {
    4.         if(start == end) return nums[start];
    5.         int mid = (start + end)>>1;
    6.         int left = dfs(start, mid, nums);
    7.         int right = dfs(mid + 1, end, nums);
    8.         int maxval1 = nums[mid], acc = nums[mid];
    9.         for(int i = mid - 1; i >= start; i--)
    10.         {
    11.             acc += nums[i];
    12.             maxval1 = max(maxval1, acc);
    13.         }
    14.         int maxval2 = 0;
    15.         acc = 0;
    16.         for(int i = mid + 1; i <= end; i++)
    17.         {
    18.             acc += nums[i];
    19.             maxval2 = max(maxval2, acc);
    20.         }
    21.         return  max(max(left, right), maxval1 + maxval2);
    22.     }
    23. public:
    24.     int maxSubArray(vector<int>& nums) {
    25.         return dfs(0, nums.size() - 1, nums);
    26.     }
    27. };