https://leetcode.cn/problems/maximum-subarray/submissions/575775026/

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
      //dp表i位置表示以该位置为结尾的子数组的最大值
      //子数组分为两种
      //长度等于1
      //长度大于1
      int n=nums.size();
      vector<int> dp(n);
      dp[0]=nums[0];
      int _max=dp[0];
      for(int i=1;i<n;i++)
      {
        dp[i]=max(nums[i],dp[i-1]+nums[i]);
        _max=max(_max,dp[i]);
      }
      return _max;
    }
};