53. 最大子数组和

一、贪心

使用count进行计数，每次与下一元素求和后判断是否大于result，若大于（即出现更大的子数组），记录result
判断count是否小于0，若小于0（即前面的子数组会对后面的数组产生负面的影响）

  1. class Solution {
  2. public:
  3.     int maxSubArray(vector<int>& nums) {
  4.         int result = INT_MIN;
  5.         int count = 0;
  6.         for(int i =0;i<nums.size();i++)
  7.         {
  8.             count += nums[i];
  9.             if(count>result)    
  10.                 result = count;
  11.             if(count<=0)count=0;
  12.         }
  13.         return result;
  14.     }
  15. };

二、动态规划

  • 状态定义： dp[i]以i元素结尾的最大连续子数组和
  • 状态转移方程：dp[i] = max(dp[i - 1] + nums[i], nums[i]);
    ```cpp class Solution { public: int maxSubArray(vector& nums) {
    1.   if (nums.size() == 0) return 0;
    2.   vector<int> dp(nums.size(), 0); // dp[i]表示包括i之前的最大连续子序列和
    3.   dp[0] = nums[0];
    4.   int result = dp[0];
    5.   for (int i = 1; i < nums.size(); i++) {
    6.       dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式
    7.       if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值
    8.   }
    9.   return result;
    } };

class Solution { public: int maxSubArray(vector& nums) { int n = nums.size(); if(n==0)return 0; //dp[n]以n为结尾的子数组的和的最大值 //dp[n]=max(nums[n],dp[n-1] + nums[n]); int pre = 0; int imax = nums[0]; for(int num:nums) { pre = max(num,pre+num); imax = max(imax,pre); } return imax; } }; ```