最大子序和

1. 暴力法

工夫复杂度：O(N^2)
空间复杂度：O(1)

1. 设置两层for循环
2. 存储第一个数字的值，顺次加上前面的数字，只存储最大值

3. 依此类推

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

   2. 动静布局

   工夫复杂度：O(N)
   空间复杂度：O(1)

4. 一一加值比拟，存储最大值

5. 一旦遇到加值后的后果 < 0，则只保留之前计算的最大值，从新开始下一个加值比拟

   class Solution{public: int maxSubArray(vector<int> &nums) {     int result = INT_MIN;     int numsSize = int(nums.size());     //dp[i]示意nums中以nums[i]结尾的最大子序和     vector<int> dp(numsSize);     dp[0] = nums[0];     result = dp[0];     for (int i = 1; i < numsSize; i++)     {         dp[i] = max(dp[i - 1] + nums[i], nums[i]);         result = max(result, dp[i]);     }     return result; }};

   3.贪婪算法

   工夫复杂度：O(N)
   空间复杂度：O(1)
   与动静布局基本一致

   class Solution{public: int maxSubArray(vector<int> &nums) {     //相似寻找最大最小值的题目，初始值肯定要定义成实践上的最小最大值     int result = INT_MIN;     int numsSize = int(nums.size());     int sum = 0;     for (int i = 0; i < numsSize; i++)     {         sum += nums[i];         result = max(result, sum);         //如果sum < 0，从新开始找子序串         if (sum < 0)         {             sum = 0;         }     }     return result; }};

   4. 分治法

   工夫复杂度：O(nlog(n))
   空间复杂度：O(log(n))

class Solution{public:    int maxSubArray(vector<int> &nums)    {        //相似寻找最大最小值的题目，初始值肯定要定义成实践上的最小最大值        int result = INT_MIN;        int numsSize = int(nums.size());        result = maxSubArrayHelper(nums, 0, numsSize - 1);        return result;    }    int maxSubArrayHelper(vector<int> &nums, int left, int right)    {        if (left == right)        {            return nums[left];        }        int mid = (left + right) / 2;        int leftSum = maxSubArrayHelper(nums, left, mid);        //留神这里应是mid + 1，否则left + 1 = right时，会有限循环        int rightSum = maxSubArrayHelper(nums, mid + 1, right);        int midSum = findMaxCrossingSubarray(nums, left, mid, right);        int result = max(leftSum, rightSum);        result = max(result, midSum);        return result;    }    int findMaxCrossingSubarray(vector<int> &nums, int left, int mid, int right)    {        int leftSum = INT_MIN;        int sum = 0;        for (int i = mid; i >= left; i--)        {            sum += nums[i];            leftSum = max(leftSum, sum);        }        int rightSum = INT_MIN;        sum = 0;        //留神这里i = mid + 1，防止反复用到nums[i]        for (int i = mid + 1; i <= right; i++)        {            sum += nums[i];            rightSum = max(rightSum, sum);        }        return (leftSum + rightSum);    }};